Лабораторна робота 13-14

Тема: Розв’язування систем лінійних рівнянь методом простої ітерації, Зейделя.

Мета: Навчитися розв’язувати системи лінійних рівнянь методом ітерації. Зейделя.

Теоретичні відомості:

Постановка задачі.

У процесі вивчення різних питань економіки, природознавства, техніки тощо доводиться розв’язувати системи лінійних алгебраїчних рівнянь. Зокрема, до таких систем зводиться чисельне розв’язування лінійних диференціальних та інтегральних рівнянь, за допомогою яких описуються реальні процеси.

Позглянемо ситему n лінійних рівнянь з n змінними:

(1)

Систему (1) можна записати компактніше .

Розв’язком системи (1) називається така впорядкована сукупність чисел с₁, с₂, ..., с_n, яка буде підставленою в (1) замість змінних х₁, х₂, ...,х_n перетворює всі рівняння в числові тотожності.

Методи розв’язання систем лінійних алгебраїчних рівнянь можна розбити на дві групи: точні і наближені.

Розглянемо наближені методи розв’язання СЛАР.

Метод називається наближеним (або ітераційним), якщо він дає змогу знайти наближений розв’язок системи (1) із наперед заданою точністю шляхом виконання скінченої кількості арифметичних операцій (навіть якщо обчислення будуть проводитися без заокруглень, а коефіцієнти і вільні члени системи будуть точними числами). Точний розв’язок системи (1) за допомогою ітераційного методу можна знайти тільки теоретично, як границю збіжної числової послідовності. Розв’язок системи, знайдений за допомогою якого-небудь наближеного методу, крім похибок заокруглення, як правило, містять похибки самого методу. До наближених належать метод ітерацій, метод Зейделя та ін.

Метод ітерацій.

Нехай задано система рівнянь (1). Подамо цю систему у вигляді еквівалентної їй системи

(2)

або у вигляді .

Суть цього методу полягає в тому, що починаючи з деякого початкового наближення, на кожному кроці обчислювального процесу це наближення пов’язку поліпшують, дістаючи при цьому нове (точніше) наближення. Цей процес продовжують доки, поки розв’язок не буде знайдено з потрібною точністю.

Останню систему рівнянь будемо розв’язувати методом послідовних наближень. За початкове наближення розв’язку візьмемо деякий вектор , де - довільні числа. Тоді послідовно знаходимо перше наближення , друге наближення і т.д. Взагалі, якщо вже побудовано k-те наближення, то наступне будуємо за формулою , або в розгорнутому вигляді:

(3)

Якщо кожна з числових послідовностей має границю , тобто , то сукупність значень ( ) є розв’язком системи (2), отже і системи (1).

Таким чином, формула (3) визначає метод простої ітерації. Його алгоритм простий і зручний для обчислень на ЕОМ. Достатні умови збіжності методу простої ітерації сформульовано в наступній теоремі.

Теорема 1. Якщо матриця системи (2) задовольняє хоч одну з умов:

1. сума абсолютних значень коефіцієнтів кожного рядка матриці менша за одиницю, тобто ;

2. сума абсолютних значень коефіцієнтів кожного стовпчика матриці менша за одиницю, тобто ;

3. сума квадратів всіх коефіцієнтів кожного стовпчика матриці менша за одиницю, тобто ,

то система рівнянь (2) має єдиний розв’язок. Цей розв’язок є границею послідовності , побудованої за методом простої ітерації (3), виходячи з будь-якого початкового наближення .

На практиці часто за початкове наближення беруть стовпчик вільних членів. Алгоритм розв’язування системи (2) методом ітерацій можна записати таким чином:

1. Обчислення величини .

2. Перевірка умови l₀<1. Якщо ця умова не виконується, то метод застосовувати не варто, в протилежному випадку переходимо до пункту 3.

3. Обчислення допустимої похибки , де - точність з якою потрібно знайти розв’язок.

4. Вибір початкового наближення .

5. Обчислення наступного наближення через знайдене на попередньому кроці .

6. Перевірка умови . Якщо ця умова виконується, то ітераційний процес завершується і вектор вважають наближеним значенням розв’язку. В іншому випадку переходимо до пункту 5.

Метод Зейделя.

Нехай маємо систему

Основна ідея методу Зейделя полягає в тому, що на кожному кроці ітераційного процесу при обчисленні x^k+1 використовується уже одержані значення x^k .

Алгоритм розв’язування даної системи методом Зейделя такий як і в методі ітерацій, лише система (3) записується таким чином: