Відкрити головне меню

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

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

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

Методи не зберігаючі розрідженістьРедагувати

Метод ЯкобіРедагувати

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

Опис методуРедагувати

 

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

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

 

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

 

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

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

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

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

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

  (   , …, ).

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

Умови збіжності процесуРедагувати

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

Оцінка похибкиРедагувати

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

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

QR методРедагувати

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

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

 

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

Методи зберігаючі розрідженістьРедагувати

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

 

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

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

Див. такожРедагувати

ДжерелаРедагувати

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

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