Дипломная работа: Розробка алгоритму та програми чисельного розвязку систем лінійних алгебраїчних рівнянь з розрідженою

ділимо на коефіцієнт a₁₁ , у результаті одержуємо рівняння:

(1.2)

Потім з кожного з інших рівнянь віднімається перше рівняння, помножене на відповідний коефіцієнт a_i1 . У результаті ці рівняння перетворяться до виду:

(1.3)

Перше невідоме виявилося виключеним із усіх рівнянь, крім першого. Далі в припущенні, що , ділимо друге рівняння на коефіцієнт і виключаємо невідоме з усіх рівнянь, починаючи з третього і т.д. У результаті послідовного виключення невідомих, матриця системи рівнянь стане трикутною:

(1.4)

Сукупність проведених обчислень називається прямим ходом методу Гауса.

З m -го рівняння системи визначаємо x_m , з (m-1) -го рівняння визначаємо x_m-1 і т.д. до x₁ . Сукупність таких обчислень називають зворотнім ходом методу Гауса.

Реалізація прямого методу Гауса вимагає N~2m ² /3 арифметичних операцій, а зворотнього – N~m ² арифметичних операцій.

1.1.2 Метод Крамера

Нехай дана система лінійних рівнянь, в якій число рівнянь дорівнює числу невідомих:

(1.5)

Припустимо, що визначник системи d ≠0. Якщо тепер замінити послідовно у визначнику стовпці коефіцієнтів при невідомих x_j стовпцем вільних членів b _i , то вийдуть відповідно n визначників d₁ ,...,d_n .

Теорема Крамера. Система n лінійних рівнянь з n невідомими, визначник якої відмінний від нуля, завжди сумісна і має єдинийрозв’язок, який обчислюється по формулах:

(1.6)

Розв’язок довільних систем лінійних рівнянь. Нехай

(1.7)

довільна система лінійних рівнянь, де число m рівнянь системи менше числа n невідомих. Тоді в матриці СЛАР знайдуться r≤ m лінійно незалежних рядків, а інші m- r рядків виявляться їхніми лінійними комбінаціями. Перестановкою рівнянь можна добитися того, що ці r лінійно незалежних рядків займуть перші r місць.

Звідси випливає, що кожне з останніх m- r рівнянь системи (1.7) можна представити як суму перших r рівнянь (які називаються лінійно незалежними або базисними), узятих з деякими коефіцієнтами. Тоді система еквівалентна наступній системі r рівнянь з n невідомими:

(1.8)

Припустимо, що мінор r -їрозмірності, складений з коефіцієнтів при перших r невідомих, відмінний від нуля: М_r ≠0, тобто є базисним мінором. У цьому випадку невідомі, коефіцієнти при яких складають базисний мінор, називаються базисними невідомими, а інші n-r – вільними невідомими.

У кожному з рівнянь системи (1.8) перенесемо в праву частину всі члени з вільними невідомими x _r+1 ,...,x_n . Тоді одержимо систему, яка містить r рівнянь з r базисними невідомими. Оскільки визначник цієї системи є базисний мінор M_r , то система має єдинийрозв’язок щодо базисних невідомих, який можна знайти по формулах Крамера. Даючи вільним невідомим довільні числові значення, одержимо загальнийрозв’язок вихідної системи.

Однорідна система лінійних рівнянь. Нехай дана однорідна система лінійних рівнянь з n невідомими:

(1.9)

Оскільки додавання стовпця з нулів не змінює рангу матриці системи, то на підставі теореми Кронекера-Kaпeллі ця система завжди сумісна і має, принаймні, нульовийрозв’язок. Якщо визначник системи відмінний від нуля і число рівнянь системи дорівнює числу невідомих, то по теоремі Крамера нульовийрозв’язок є єдиним.

У тому випадку, коли ранг матриці системи менше числа невідомих, дана система крім нульового розв’язку буде мати і ненульові розв’язки. Для знаходження цих розв’язків у системі (1.9) виділяємо r< n лінійно незалежних рівнянь, інші відкидаємо. У виділених рівняннях у лівій частині залишаємо r базисних невідомих, а інші n-r вільних невідомих переносимо в праву частину. Тоді приходимо до системи, розв’язуючи яку по формулах Крамера, виразимо r базисних невідомих x₁ ,...,х_r через n-r вільних невідомих.

1.1. 3 Метод головних елементів

Нехай дана система n лінійних рівнянь з n невідомими:

(1.10)

де елементи a_ij ( i, j=1,…, n) утворюють розширену матрицю системи . Виберемо найбільший по модулю і не належачий стовпцю вільних членів елемент a_pq матриці, який називається головним елементом, і обчислимо множники m_i =- a_iq / a_pq для всіх рядків з номерами i≠ p (р -й рядок, що містить головний елемент, називається головним рядком).

Далі до кожного другорядного i -го рядку додамо головний рядок, помножений на відповідний множник m_i .

У результаті одержимо нову матрицю, усі елементи q -го стовпця якої, крім a_pq , складаються з нулів.

Відкинувши цей стовпець і головний p -й рядок, одержимо нову матрицю, число рядків і стовпців якої на одиницю менше. Повторюємо ті ж операції з отриманою матрицею, після чого одержуємо нову матрицю і т.д.