Ітераційні методи розв'язування СЛАР

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Ітераційні методи або ж методи ітерацій розв'язування СЛАР — наближені методи розв'язку проблеми знаходження власних значень та власних векторів (що еквівалентно розв'язку СЛАР), які базуються на покроковому наближені (знаходження по наближеному значенню величини наступного наближення) до їх точних значень, минуючи вичислення характеристичного многочлена. Ітераційні методи дозволяють отримати значення коренів системи із заданою точністю у вигляді границі послідовності деяких векторів (ітераційний процес). Характер збіжності і сам факт збіжності методу залежить від вибору початкового (нульового) наближення, кореня .

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

Методи не зберігаючі розрідженість[ред.ред. код]

Метод Якобі[ред.ред. код]

Докладніше: Метод Якобі

Опис методу[ред.ред. код]

АХ = В — у матричному вигляді.

Припускаючи, що  ; (,, …,), виразимо через перше рівняння,  — через друге і т. д.
Позначимо:


,,…,; ,,…,; Система приведена до нормального вигляду.

=+х — система у матричному вигляді.

За нульове наближення приймемо стовпець вільних членів.

 — нульове наближення;

 — I наближення;

 — II наближення і т. д.;

(, …,).

 — розв'язання системи.

Умови збіжності процесу[ред.ред. код]

Метод ітерації застосовують у випадку, якщо сходиться послідовність наближень по вказаному алгоритму. Умови збіжності : (де ,,…,) або (де,,…,;).

Оцінка похибки[ред.ред. код]

, де -точність,  — вектор точних значень.

 — одна з трьох норм матриці , — одна з трьох норм матриці .

QR метод[ред.ред. код]

Докладніше: QR алгоритм

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

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

Методи зберігаючі розрідженість[ред.ред. код]

Основними для задач високого порядку (тисячі, десятки тисяч рядків і стовпців) є методи, елементарна операція яких — перемноження матриці на вектор. Припустимо, що власні значення матриці занумеровані спадаючими за модулем (). Найбільш широку область застосування має степеневий метод для обчислення власного значення, найбільшого за модулем, . Виходячи з початкового наближення будується послідовність нормованих векторів:

Така послідовність сходиться якщо: (1) Всі елементарні дільники матриці , що відносяться до  — лінійні (2) немає інших власних значень з таким модулем, (3) в розкладі нульового наближення по кореневому базису присутня нетривіальна компонента по власному підросторі . Сходимість в цьому методі не надто швидка, як правило, і визначається відношенням двох старших по модулю власних значень.

Важливими є також метод обернених ітерацій та метод Стюарта, що теж визначають власні значення по одному. Для одночасного їх пошуку існує метод Ланцоша.

Див. також[ред.ред. код]

Джерела[ред.ред. код]

  • И. М. Виноградов. Математическая энциклопедия. Том 2.. — Москва : «Советская энциклопедия», 1985. — Т. 2. — С. 686-689.
  • Даніліна Н. І., Дубровська Н. С., Кваша О. П., Смирнов Г. Л., Феклісов Г. І."Чисельні методи: Посібник

для технікумів." Видання «Вища школа»,1976