Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Прикладна математика
Кафедра:
Не вказано
Інформація про роботу
Рік:
2003
Тип роботи:
Методичні вказівки
Предмет:
Чисельні методи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ЧИСЕЛЬНЕ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
МЕТОДИЧНІ ВКАЗІВКИ
з курсу "Чисельні методи"
для студентів базового напрямку
6.0802 "Прикладна математика"
Затверджено
на засіданні кафедри
“Прикладна математика”
Протокол № 5 від 28.11.2002 р.
Львів 2003
Чисельне розв’язування систем лінійних алгебраїчних рівнянь: Методичні вказівки з курсу «Чисельні методи» для студентів базового напрямку 6.0802 «Прикладна математика»/ Укл.: М.В.Кутнів, І.П.Мединський, Я.В.Пізюр. – Львів: Видавництво Національного університету «Львівська політехніка», 2003.- 35 с.
Укладачі Кутнів М.В., канд. фіз-мат. наук, доц.
Мединський І.П., канд. фіз-мат. наук
Пізюр Я.В., канд. фіз-мат. наук, доц.
Відповідальний за випуск Костробій П.П., канд. фіз-мат. наук, проф.
Рецензенти Максимів Є.М., канд. фіз-мат. наук, доц.,
Гнатів Б.В., канд. фіз-мат. наук, доц.
Теоретична частина
§1. Прямі методи розв’язування систем лінійних алгебраїчних рівнянь
В §1-3 розглядаються чисельні методи розв’язування систем лінійних алгебраїчних рівнянь (СЛАР)
, (1)
де – матриця порядку , -невідомий вектор, - заданий вектор. Будемо припускати, що визначник матриці відмінний від нуля, так що розв’язок системи існує і єдиний.
Методи чисельного розв’язування систем (1) ділять на два типи: прямі і ітераційні. За допомогою прямих (або точних) методів розв’язок СЛАР знаходять за скінченне число арифметичних дій. Відмітимо, що внаслідок похибок заокруглень при розв’язуванні задач на ЕОМ прямі методи не дають точного розв’язку і називати їх точними можна тільки нехтуючи похибками заокруглень. Порівняння різних прямих методів проводиться за кількістю арифметичних дій за великих , необхідних для одержання розв’язку. Перевага надається за інших рівних умов методу з меншим числом дій. З курсу алгебри відомі два основні методи розв’язування СЛАР: формули Крамера та метод виключення (метод Гаусса). За великих перший спосіб, який грунтується на обчисленні визначників вимагає порядку дій, тоді як метод Гаусса тільки дій. Тому метод Гаусса в різних варіантах широко використовують при розв’язуванні на ЕОМ задач лінійної алгебри.
Ітераційні методи полягають в тому, що розв’язок системи (1) знаходять як границю при послідовності наближень , де –номер ітерації. Як правило за скінченне число ітерацій ця границя не досягається. Задається деяке достатньо мале число (точність) і обчислення проводяться до тих пір, поки не виконається оцінка .
Метод Гаусса
Запишемо систему (1) у вигляді
(2)
Метод Гаусса розв’язування системи (2) полягає у послідовному виключенні змінних з цієї системи.
Припустимо, що . На першому кроці від -го рівняння системи (2) віднімаємо перше рівняння, помножене на . У результаті одержимо систему
(3)
де Якщо то з останніх рівнянь системи (3) можна виключити
На кроці прямого ходу матимемо систему рівнянь:
(4)
Припустимо, що Помножимо те рівняння системи (4) на і віднімемо від го, де Унаслідок одержимо
де
(5)
Елемент на му кроці виключення називають головним елементом.
При реалізації алгоритму елементи можна записувати відповідно на місце вихідних елементів пам’яті ЕОМ, а елементи на місце елементів які перетворені в нуль.
Після закінчення прямого ходу отримаємо систему рівнянь із верхньою трикутною матрицею:
(6)
З цієї системи визначимо невідомі за формулами:
(7)
Систему лінійних рівнянь розв’язано.
Обчислимо число арифметичних дій необхідних для розв’язання системи (2) методом Гаусса. Оскільки виконання операцій множення і ділення на ЕОМ потребує значно більше часу, ніж виконання додавання і віднімання, обмежимося обчисленням множень і ділень. Розглянемо спочатку прямий хід. На му кроці для обчислення необхідно ділень, а для обчислення за формулами (5) множень. Отже, обчислення елементів матриці системи (6) потребує операцій множення та ділення. Обчислення правих частин за формулами (5) вимагає множень. Для прямого ходу методу Гаусса необхідно виконати операцій множення та ділення. За великих це число дій дорівнює приблизно . Для здійснення оберненого ходу методу Гаусса за формулами (7) потрібно операцій множення та ділення. Отже, для великих число дій множення і ділення у методі Гаусса приблизно дорівнює
Метод Гаусса компактно записують в матричній формі. Покажемо, як при цьому цей метод зв’язаний з розкладом ( факторизацією ) матриці .
Введемо нижню трикутну матрицю:
,
яку називають також матрицею Фробеніуса. Тоді -й крок виключення еквівалентний множенню системи (4) на зліва. Зауважимо, що
.
Справджується також і більш загальне твердження де верхня трикутна матриця системи (6).
Метод виключення Гаусса еквівалентний такому процесу:
виконати розклад матриці;
розв’язати систему рівнянь ;
розв’язати систему .
Така матрична форма алгоритму Гаусса зручна при розв’язанні послідовності систем лінійних алгебраїчних рівнянь з однією і тією ж матрицею і різними правими частинами, оскільки в цьому випадку достатньо лише один раз здійснити розклад матриці і розв’язати послідовність систем з трикутними матрицями. Процес розкладу матриці потребує операцій множення, тоді як розв’язування системи рівнянь із трикутною матрицею порядку операцій.
За допомогою методу виключення можна обчислити також визначник матриці . Справді, оскільки визначник добутку двох матриць є добутком їх визначників, унаслідок розкладу матриці маємо
Отже, визначник є добутком діагональних елементів приведеної до трикутного виду матриці і для обчислення потрібно тільки додаткових множень.
Процес виключення Гаусса є також найкращим методом обертання матриці . Нехай вектор, й елемент якого дорівнює , а решта нульові. Тоді вектор буде м стовпцем одиничної матриці і з співвідношення випливає, що й стовпець матриці є розв’язком системи лінійних рівнянь . Отже, розв’язуючи систем рівнянь
(8)
і, використовуючи знайдені вектори як стовпці, одержимо обернену матрицю . Для ефективного розв’язування задачі (8) з однією і тією ж матрицею можна використати метод виключення Гаусса у вигляді розкладу.
Неважко показати, що метод Гаусса можна застосувати лише в тому разі, коли всі головні мінори відмінні від нуля. Основна ідея полягає в тому, щоб на черговому кроці виключити ту невідому, коефіцієнт при якій найбільший за модулем. Цього можна досягнути перестановкою рядків системи. За головний елемент у цьому алгоритмі беруть найбільший за модулем елемент. Тоді, якщо , то у процесі обчислень не буде ділення на нуль. й крок алгоритму Гаусса з вибором головного елемента у стовпчику має вигляд:
1. Знайти таке, що Якщо то вироджена і алгоритм закінчуємо, інакше поміняти місцями і а також і .
2. Обчислити
і
за формулами (5).
Зауважимо, що в алгоритмі з вибором головного елемента
Крім вибору головного елемента в стовпчику, можна вибрати головний елемент у рядку, а також у всій матриці. Алгоритм вибору головного елемента у двовимірному масиві (матриці) використовують рідко через велику кількість операцій.
Опишемо тепер метод Гаусса у вигляді розкладу з вибором головного елемента у стовпчику.
При перестановці рядків матриці алгоритм виключення Гаусса не буде еквівалентний розкладу матриці на добуток нижньої і верхньої трикутних матриць. Однак його можна модифікувати.
Введемо матрицю переставлень розміру , у кожному рядку і кожному стовпці якої є лише один елемент, відмінний від нуля і рівний одиниці. Переставлення рядків матриці може бути здійснено за допомогою множення зліва на відповідну матрицю переставлень . Нехай матриця переставлень, отримана з одиничної матриці тим же переставленням рядків, що застосовувалося на му кроці виключення. Тоді послідовно домножуючи матрицю зліва на здійснимо трикутну факторизацію :
де - матриця переставлень. Як відомо, обернена матриця до матриці переставлень є матрицею переставлень. Отже, і перший множник у розкладі є переставленням нижньої трикутної матриці, а другий як і раніше верхньої трикутної матриці. Якщо на -му кроці ніяких переставлень не здійснюється, то матриця є одиничною матрицею.
Використання методу Гаусса з вибором головного елемента потребує додаткових затрат для переставляння рядків, тому для систем, стосовно яких відомо, що переставляння рядків не потрібне, ефективнішим є використання звичайного методу Гаусса. Серед таких систем найбільш вживані - системи з діагонально переважаючими та додатно визначеними матрицями.
Унаслідок впливу похибок заокруглень метод Гаусса дозволяє одержати лише наближений розв’язок системи (1). Якщо обчислення проведені з великою похибкою, то можна використати ітераційне уточнення розв’язку, кожен крок якого описується формулами:
,
, (9)
Розв’язування системи (1) зводиться до розв’язування трикутних систем
,
що вимагає порядку операцій.
Приклад 1. Методом Гаусса обчислити визначник матриці
.
Розв’язування. Оскільки , то проведемо обчислення за схемою
Тоді .
Приклад 2. Методом виключення Гаусса з вибором головного елемента у стовпчику розв’язати СЛАР
Розв’язування. Оскільки головний елемент у першому стовпці матриці системи , то переставляти рівняння на першому кроці не потрібно. Знайдемо
і одержимо систему
На другому кроці головний елемент , а тому переставимо другий і третій рядки системи
Використовуючи обернений хід метода Гаусса, знайдемо .
Приклад 3. Методом – розкладу з вибором головного елемента розв’язти СЛАР
,
де
.
Розв’язування. Оскільки , то головний елемент у першому стовпці , а тому переставимо перший і другий рядки матриці . Тоді одержимо
,
де – матриця переставлень отримана з одиничної матриці переставлянням першого та другого рядків, тобто
.
Обчислимо
тоді
,
.
На другому кроці головний елемент , а тому переставимо другий і третій рядки матриці . Тоді одержимо
де
.
Обчислимо
,
.
Тоді
.
З рівності випливає, що
.
На підставі , вихідна система еквівалентна системі
.
Розв’яжемо спочатку СЛАР з нижньою трикутньою матрицею
або
Звідси . Оскільки , то знайдемо розв’язок системи з правою трикутною матрицею
Звідси .
Метод прогонки
Найвідоміший різновид методу Гаусса – метод прогонки, який застосовують до систем з тридіагональними матрицями. Такі системи часто зустрічаються при розв’язанні крайових задач для звичайних диференціальних рівнянь другого порядку і рівнянь із частинними похідними методом сіток. Вони можуть бути записані у вигляді:
(9)
або
,
де – вектор невідомих, – вектор правих частин , а – тридіагональна матриця розміру :
.
Унаслідок прямого ходу в методі Гаусса одержимо систему з дводіагональною верхньою трикутною матрицею. Тому формули зворотнього ходу мають вигляд:
, (10)
де – неозначені коефіцієнти. Для визначення підставимо у -те рівняння системи (9):
. (11)
Рівняння (11) розв’яжемо відносно , тоді
. (12)
Порівнюючи рівність (10) і (12) , одержимо
. (13)
З першого рівняння системи (9)
.
Отже,
.
Визначивши послідовно обчислимо за формулами (13).
Для обчислення за формулою (10) необхідно задати . Підставимо
в останнє рівняння системи (9), тоді
,
.
Отже алгоритм методу прогонки має вигляд:
1. Обчислимо коефіцієнти
,
. (14)
2. Знаходимо розв’язок
. (15)
Для реалізації алгоритму методу прогонки необхідно множень, ділень і додавань.
Метод прогонки (14), (15) за допомогою якого обчислюють справа наліво, називають правою прогонкою.
Зауважимо, що коефіцієнти не залежать від правої частини системи (9), а визначаються лише величинами . Тому, якщо необхідно розв’язувати послідовність задач з різними правими частинами, але з однією і тією ж матрицею, то коефіцієнти обчислюються лише при розв’язуванні першої задачі з послідовності. Для кожної подальшої задачі визначаються тільки коефіцієнти і розв’язок .
Формули прогонки можна застосувати, якщо знаменники в (14) не перетворюються в нуль. Крім того, при обчисленні за рекурентною формулою (15 ) похибки заокруглень можуть нагромаджуватися. Дійсно, нехай при обчисленні допущена похибка , тобто знайдено . Тоді . Звідси випливає, що за умови похибка може сильно зростати. Якщо виконується умова , то і кажуть, що метод прогонки стійкий.
Доведемо, що для виконання нерівностей , достатньо, щоб коефіцієнти системи (9) задовільняли умови переваги діагональних елементів
, (16)
, (17)
причому хоча б в одній з нерівностей (16) або (17) виконувалася строга нерівність. З умови (17) випливає , що . Припустимо , що , тоді на підставі (16)
, (18)
тобто і
.
Покажемо, що . Для цього використаємо припущення, що хоча б в одній з нерівностей (16) або (17) виконується строга нерівність. Якщо , то і . Якщо строга нерівність досягається в (16) для деякого , то з (18) одержимо, що і . За індукцією для . Отже, в цьому випадку будемо мати , і тому . Якщо , то нерівність виконується , починаючи з . Тому знову дістанемо і .
§2. Норми та обумовленість матриць систем лінійних алгебраїчних рівнянь
Коефіцієнти матриці і правої частини СЛАР не завжди відомі точно. Навіть, якщо ці величини відомі точно, виникають похибки заокруглень. Можна показати, що похибки заокруглень у методі Гаусса мають такий самий вплив на результат, що і похибки у вихідних коефіцієнтах. Тому фактично маємо розв’язок деякої іншої системи
. (1)
На практиці важливо знати відносну похибку для якої небудь векторної норми. Найчастіше використовують норми вектора
і узгоджені з ними норми матриць (тобто для яких )
,
,
,
де -максимальне власне значення матриці , а називається максимальним сингулярним числом матриці . Якщо замість (1), брати модель обчислень
, (2)
тобто вважати, що матриця задана в ЕОМ точно, то з ланцюжка співвідношень
випливає оцінка
, (3)
де (відповідно ) називається числом обумовленості матриці і, як показує оцінка (3), це число є мірою невизначеності розв’язку системи (1) при неточних вхідних даних.
Якщо брати модель обчислень
,
в якій збурені елементи лише матриці , а праві частини задані точно, то використовуючи співвідношення , дістанемо
,
,
, (4)
тобто і в цьому випадку число є мірою невизначеності розв’язку при неточних вхідних даних і інтервал цієї невизначеності тим ширший, чим більша величина . Можна довести, що таку саму роль відіграє число обумовленості і у випадку моделі обчислень (1).
Кажуть, що СЛАР погано обумовлена, якщо малі зміни елементів матриці або правих частин викликають великі зміни у розв’язку. У цьому випадку ніякий чисельний метод не дає точного розв’язку, а у багатьох випадках навіть не варто шукати розв’язок.
Матриці погано обумовлених СЛАР мають відносно велике число обумовленості. Такі матриці називають погано обумовленими. Це означення залежить від норми і від ЕОМ, на яких здійснюється обчислення: одна і та ж сама система на різних ЕОМ може бути добре чи погано обумовленою. Якщо число обумовленості велике, то ( див. (3), (4) ) малі зміни даних можуть привести до великих змін розв’язку.
Приклад 4. Обчислити числа обумовленості матриці
.
Розв’язування. Обчислимо матрицю
.
Тоді ; ; ; а ; ; .
§3. Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь
Приклади та канонічний вигляд ітераційних методів
Розглянемо СЛАР:
, (1)
де – матриця розміру , – невідомий вектор, – заданий вектор.
Для побудови ітераційного методу розв’язування системи (1) попередньо перетворимо –те рівняння системи (1) до вигляду
.
Цю систему будемо розв’язувати методом послідовних наближень
, (2)
де – –та ітерація – ої компоненти вектора . Початкові наближення задаються довільно. Ввівши позначення
,
ітераційний метод (2) запишемо у вигляді
. (3)
Припустимо, що всі відмінні від нуля. Систему (1) перетворимо до вигляду
. (4)
Будемо вважати, що значення суми дорівнює нулю, якщо верхня границя сумування менша за нижню. Отже, запишемо рівняння (4) при
.
В методі Якобі виходять з запису системи у вигляді (4), причому ітерації визначають так:
. (5)
Ітераційний метод Зейделя має вигляд
. (6)
Щоб зрозуміти, як знаходять звідси значення , запишемо детальніше перші два рівняння системи (6):
(7)
. (8)
Перша компонента вектора знаходиться з рівняння (7) явно, для її обчислення потрібно знати вектор і значення . При знаходженні з рівняння (8) використовуються тільки що знайдені значення і відомі значення , з попередньої ітерації. Таким чином, компоненти вектора знаходяться з рівняння (5) послідовно, починаючи з .
Щоб записати ітераційні методи Якобі та Зейделя в матричному вигляді, матрицю системи (1) подамо у вигляді суми трьох матриць
, (9)
де
.
Тоді ітерації Якобі (5) можна записати у вигляді
або
. (10)
Метод Зейделя (6) записується у вигляді
або
. (11)
Враховуючи (9), методи (10), (11) можна переписати відповідно у вигляді
. (12)
. (13)
Для прискорення збіжності в ітераційних методах вводять числові параметри, які, взагалі кажучи, залежать від номера ітерації. Наприклад, в методах (3), (12) можна ввести ітераційні параметри так:
,
.
Узагальненням методу Зейделя (13) є метод верхньої релаксації
, (14)
де – заданий числовий параметр. Для отримання розрахункових формул перепишемо (14) у вигляді
або у покомпонентному записі
.
В теорії ітераційних методів існує дві основні проблеми: а) при яких значеннях параметрів метод збіжний; б) при яких значеннях параметрів збіжність буде найбільш швидкою (відповідні параметри називаються оптимальними). Надалі ми детальніше зупинимося на цих питаннях.
Наведені нижче методи послідовних наближень, Якобі та Зейделя відносяться до однокрокових або двоярусних ітераційних методів, оскільки для знаходження використовують лише одну попередню ітерацію . Якщо виражається через і , то метод називають двокроковим або триярусним. Надалі ми будемо розглядати лише двоярусні ітераційні методи.
Один і той самий ітераційний метод можна записати багатьма різними способами. Тому доцільно ввести деякий стандартний вигляд запису ітераційних методів.
Канонічним виглядом двоярусного ітераційного методу називається ітераційна схема
(15)
де –матриця, для якої існує обернена . Числа називають ітераційними параметрами. Якщо , тобто не залежать від , то метод (15) називають стаціонарним, у протилежному випадку – нестаціонарним. При ітераційну схему називають явною, тому що тоді знаходять за явною формулою
При метод (15) називають неявним, бо для знаходження необхідно розв’язати операторне рівняння
(16)
У неявних методах оператор вибирають так, щоб рівняння (16) можна було розв’язати простіше, ніж (1).
Матричні нерівності та дії з ними
Нехай – –вимірний евклідовий простір зі скалярним добутком
.
Для дійсної матриці нерівність означає, що . З нерівності випливає, що . Дійсно, якщо – несиметрична матриця, то для маємо
,
де – матриця, транспонована до . Тому за можна взяти мінімальне власне значення матриці . З оцінки випливає, що існує матриця . Нерівність означає, що . Якщо , то може не існувати.
Наведемо потрібні надалі відомості з лінійної алгебри.
1). Якщо – дійсна симетрична матриця, то існує ортогональна матриця (тобто ) така, що , де – діагональна матриця. На головній діагоналі матриці знаходяться власні значення матриці .
2). Для симетричної матриці нерівність () еквівалентна невід’ємності (додатності) всіх її власних значень.
Доведення. Використовуючи властивість 1, одержимо
,
де – власні числа матриці , – –та компонента вектора . Звідси випливає, що якщо , (), то (). Навпаки, нехай – власне значення матриці . Задамо вектор , у якого всі компоненти, крім –ої дорівнюють нулю, а . Оскільки матриця існує, для заданого вектора знайдеться вектор такий, що . Але тоді
,
тобто .
3). Якщо , то .
Доведення. Згідно з властивістю 2 всі власні числа матриці додатні, отже, і .
4). Для симетричної матриці і для еквівалентні такі нерівності
, (17)
. (18)
Доведення. Згідно звластивістю 2 умова (17) еквівалентна нерівностям
,
де – власні числа матриці . Звідси , що в свою чергу еквівалентне (18).
5). Якщо і (), то існує матриця , яка володіє такою властивістю
. (19)
Ця матриця називається квадратним коренем з матриці і позначається .
Доведення. Нехай – власні числа матриці . Згідно з властивістю 1 існує ортогональна матриця така, що
.
Оскільки всі невід’ємні, можна визначити матрицю як
.
Тоді матриця володіє властивістю (19).
6). Нехай і – невироджена матриця. Тоді еквівалентні нерівності
.
Аналогічно, еквівалентні строгі нерівності
.
Доведення. Для маємо . Отже, , якщо . Доведемо обернене. Оскільки існує, то довільний вектор можна подати у вигляді , де . Тоді
,
тобто .
7). Якщо і – симетричні і – невироджена матриця, то еквівалентні нерівності
.
Доведення випливає з попередньої властивості.
8). Нехай і – довільні дійсні числа. Тоді еквівалентні нерівності
.
Доведення. Згідно з влативістю 5 існує матриця . Використовуючи властивість 7, перейдемо від першої нерівності до другої за допомогою таких нерівностей:
,
,
.
9). Нехай і – довільні числа. Тоді еквівалентні нерівності
.
Доведення. Помножимо першу нерівність зліва і справа на , тоді одержимо
.
Згідно з властивістю 8 остання нерівність еквівалентна нерівності , тобто
,
помноживши котру зліва і справа на , одержимо .
Дослідження збіжності ітераційних методів
Розглянемо стаціонарний ітераційний метод
. (20)
Похибка ітераційного методу характеризується вектором , який згідно з (1), (20) задовільняє однорідне рівняння
. (21)
Кажуть, що ітераційний метод (20) збігається, якщо при .
Якщо існує , то з рівняння (21) знайдемо
, (22)
де . Тоді
. (23)
Отже, за умови що маємо при , тобто ітераційний метод збігається зі швидкістю геометричної прогресії з знаменником .
Зокрема, ітераційний метод простої ітерації (3) збіжний за умови, що .
Розв’язок системи (1) будемо надалі розглядати як елемент – вимірного простору зі скалярним добутком та нормою .
Теорема1. Нехай – симетрична додатно визначена матриця, і виконується умова
. (24)
Тоді ітераційний метод (20) збігається.
Доведення. Покажемо спочатку, що за умови (24) числова послідовність незростаюча. З рівняння (22) знаходимо
.
Тоді
.
Оскільки матриця – симетрична, то
,
а тому
. (25)
Звідси, враховуючи умову (24), одержимо нерівність
Отже,
,
тобто послідовність – незростаюча і обмежена знизу нулем. Тому за теоремою Веєрштраса існує границя
. (26)
Доведемо, що . З додатності матриці випливає її додатна визначеність, тобо існує константа така, що
.
Звідси і з (25) випливає нерівність
.
Враховуючи (26) перейдемо в цій нерівності до границі при , тоді одержимо
,
де . На підставі того, що – додатно визначена, а тому існує обернена , будемо мати
.
Звідси випливає, що
.
Застосуємо цю теорему до конкретних ітераційних методів.
Наслідок 1. Нехай – симетрична додатно визначена матриця з діагональною перевагою, тобто
. (27)
Тоді метод Якобі (12) збігається.
Доведення. Оскільки для методу Якобі , а , то умова (24) має вигляд . Покажемо, що ця матрична нерівність випливає з (27). Оцінимо квадратичну форму
.
З умов симетричності та додатної визначеності матриці маємо , а тому з попередньої оцінки випливає нерівність
. (28)
Перепишемо умову (27) у вигляді
.
Тоді з нерівності (28) одержимо
.
Наслідок 2. Нехай – симетрична додатно визначена матриця. Тоді метод верхньої релаксації (14) збігається за умови . Зокрема, метод Зейделя () збіжний.
Доведення. Метод верхньої релаксації (14) має канонічний вигляд (20) з . Оскільки матрицю системи (1) можна записати у вигляді (9), то для симетричної матриці матриця є транспонованою до , а тому
.
Умова збіжності (24) має вигляд
і при виконується.
Розглянемо збіжність методу простої ітерації
(29)
з симетричною додатно визначеною матрицею . Згідно з (24) метод збігається за умови
. (30)
Нехай – власні значення матриці , які розташовані в порядку зростання. Умова (30) еквівалентна тому, що всі власні значення матриці додатні. Достатньо вимагати додатності мінімального власного числа цієї матриці, рівного . Таким чином, ітераційний метод (29) збігається, якщо
, (31)
де – максимальне власне число матриці .
Умова (31) є крім того необхідною для збіжності (29), тобто, якщо (31) не виконується, то знайдеться таке початкове наближення , при якому .
Доведемо останнє твердження. Візьмемо за початкове наближення вектор , де – точний розв’язок системи (1), а – власний вектор матриці , який відповідає власному числу , тобто . При такому виборі початкового наближення
.
З рівняння (23)
,
а тому .
Якщо , то . Якщо ж , то і . Отже, умова (31) необхідна і достатня для збіжності методу простої ітерації (29).
Теорема 2 (необхідна і достатня умова збіжності двоярусного ітераційного методу). Ітераційний метод (20) збігається до розв’язку системи (1) для будь–якого початкового наближеня тоді і тільки тоді, коли всі власні значення матриці за модулем менші від 1.
Доведення. Доведемо спочатку необхідність. Нехай власні значення, такі що і відповідний власний вектор матриці . Тоді при початковому наближенні маємо і з (23) при
Доведення достатності наведемо тільки для випадку, коли матриця має лінійно незалежних власних векторів. Нехай власні числа матриці і відповідні лінійно незалежні власні вектори. Розкладемо величину за власними векторами :
Тоді
і
(32)
де спектральний радіус матриці З оцінки (32) на підставі припущення теореми 2 а тому метод збіжний. В загальному випадку, коли система власних векторів матриці неповна, то доведення достатності умов теореми проводиться за допомогою зведення до жорданової форми.
Оцінка швидкості збіжності стаціонарних ітераційних методів
У п. 3 доведено, що ітераційний метод (20) збігається зі швидкістю геометричної прогресії, тобто, що виконується оцінка
. (33)
Використовуючи цю оцінку, можна визначити кількість ітерацій, достатніх для того, щоб початкова похибка зменшилася в задане число раз. Дійсно, задамо і будемо вимагати, щоб , тоді
.
З (33) одержимо, що
,
тобто після проведення ітерацій початкова похибка зменшиться в раз. Ціла частина числа називається мінімальним числом ітерацій необхідних для одержання заданої точності .
Вираз , який знаходиться в знаменнику , називається швидкістю збіжності ітераційного методу. Швидкість збіжності визначається властивостями матриці переходу і не залежить ні від номера ітерації , ні від вибору початкового наближення , ні від заданої точності . Чим вища швидкість збіжності, тим кращий метод.
При практичному використанні ітераційних методів велике значення має швидкість збіжності. Відповідь на це питаня дає таке твердження.
Теорема 3. Нехай і – симетричні додатно визначені матриці, для яких справджуються нерівності
. (34)
де – додатні сталі . При
ітераційний метод (20) збігається і для похибки справджуються оцінки
, (35)
, (36)
де і
Доведення. Для дослідження збіжності ітераційної схеми (20) перейдемо до задачі для еквівалентної похибки . Тоді з (22) одержимо
, (37)
де . Оскільки матриця симетрична, то
. (38)
Оскільки
,
то матричні нерівності (34) можна записати у вигляді
або (згідно з властивістю 9)
.
Помножимо останні нерівності зліва і справа на , тоді
.
Звідси
. (39)
На підставі властивості 4 нерівності (39) еквівалентні нерівності
.
Отже, з нерівності (38) випливає оцінка
,
з якої випливає оцінка (35). Дійсно,
.
Оцінка (36) доводиться аналогічно, якщо за взяти вектор , а за –матрицю .
Многочлени Чебишева
Многочлени Чебишева на відрізку визначаються співідношенням
.
Розглянемо деякі властивості цих многочленів:
1. Якщо здійснити переторення при маємо
.
В цій рівності покладемо , тоді одержимо
.
Отже, справджується рекурентне співвідношення:
,
.
Старший член многочлена отримується із старшого члена множенням на , а тому старший член при є .
2. При , отже точки екстремуму на відрізку будуть точки, де . Це точки, які визначаються формулою
причому
.
3. Введемо многочлени , причому . Отже, .
4. З рівняння отримаємо, що – корені многочлена Чебишева.
Лема. Нехай – довільний многочлен степеня зі старшим коефіцієнтом на відрізку . Серед всіх многочленів многочленом з найменшою вехньою межею (многочленом який найменше відхиляється від нуля), є многочлен , тобто
.
Доведення. Припустимо протилежне, тобто і розглянемо фнкцію , яка є многочленом степеня і відмінна тотожньо від нуля. Розглянемо значення :
.
Многочлен на відрізку міняє знак разів, тобто має коренів. Але це неможливо, тому що – многочлен степеня , відмінний від тотожнього нуля. А це протиріччя, яке доводить лему. Тому многочлени називають многочленами, які найменше відхиляються від нуля.
Розглянемо тепер многочлени Чебишева на відрізку .
6. Ітераційний метод з чебишевським набором параметрів
Розглянемо явну схему
, (40)
при
Похибка задовільняє рівняння
.
Звідси
, (41)
а
Отже, матриця є поліномом степеня відносно , коефіцієнти якого залежать лише від З (41) для одержуємо нерівність
Параметри будемо вибирати так, щоб була мінімальною. Матричний поліном
є самоспряженою матрицею, оскільки – самоспряжена.
Нехай – відповідно власні значення і власні функції матриці :
Матриця має ті самі власні функції і власні значення тому
тобто Оскільки – самоспряжена матриця, то
Власні значення матриці розміщені на відрізку а тому
Задача найкращого вибору параметрів звелася до задачі знаходження
Відобразимо відрізок на відрізок за допомогою лінійного перетворення
Тоді
.
Умова нормування має вигляд
(42)
Отже, необхідно знайти поліном , який найменше відхиляється від нуля на відрізку , тобто щоб був мінімальним і виконувалася умова нормування (42). Таким поліномом є
де – поліном Чебишева першого роду, який має вигляд
(43)
Поліном Чебишева має нулів на відрвзку , які визначаються за формулою
а поліном має нулі Враховуючи зв’язок між і буде мати нулі
,
які повинні збігатися з нулями . Звідси
Використовуючи позначення
(44)
запишемо параметри у вигляді
(45)
Знайдемо тепер
оскільки Зауважимо, що а тому, користуючись формулою (43) для , будемо мати
.
Перетворимо вираз у дужках
Звідси
Отже, для схеми (40) з набором параметрів (45), (44), яку називають чебишевським ітераційним методом ( методом Річардсона), виконується оцінка
де
Визначимо так, щоб Тоді
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора