Реферат Чисельні методи

Страница 1 из 3 | Следующая страница

МЕТОДГАУССА З ВИБОРОМ ГОЛОВНОГОЭЛЕМЕНТА.

Основна ідея методу. Може бути, що систему

>Ax=f

(1)

має єдине рішення, хоча якійсь із кутовихминоров матриці А нульовий. І тут звичайний метод Гаусса виявляється непридатним, але, можливо застосований метод Гаусса з головного елемента.

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

Різні варіанти методу Гаусса з головного елемента проілюструємо з прикладу системи з цих двох рівнянь

(2)

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

(3)

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

Застосовується також метод Гаусса з головного елемента по стовпцю. Припустимо, що .Перепишем систему (2) як

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

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

Матриці перестановок. Раніше засвідчили, що звичайний метод Гаусса можна записати як

де -елементарні нижні трикутні матриці. Щоб самому отримати аналогічну запис методу Гаусса з головного елемента, необхідно розглянути матриці перестановок.

>ОПРЕДЕЛЕНИЕ 1.

Матрицею перестановок Р називається квадратна матриця, що має у кожному рядку в кожному стовпці лише одне елемент різниться від нуля дорівнює одиниці.

>ОПРЕДЕЛЕНИЕ 2.

Елементарного матрицею перестановок називається матриця, отримана з одиничної матриці перестановкою к-й іl-й рядків.

Наприклад, елементарними матрицями перестановок третього порядку є матриці

Можна відзначити такі властивості елементарних матриць перестановок, що випливають безпосередньо з їхньої визначення .

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

Застосування елементарних матриць перестановок для описи методу Гаусса з головного елемента по стовпцю можна пояснити ось на чому прикладі системи третього порядку:

(4)

Система має вигляд (1), де

(5)

Максимальний елемент першого шпальти матриці А перебуває на другий рядку. Тому потрібно поміняти місцями другу й дослідити першу рядки - і можливість перейти до еквівалентній системі

(6)

Систему (6) можна записати як

(7)

тобто. вона виходить із системи (4) шляхом множення на матрицю

перестановок

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

У результаті системи (7) час торкнутися еквівалентній системі

(8)

чи розгорнутому вигляді

(9)

З двох рівнянь системи (9) треба тепер виключити змінне . Оскільки максимальним елементом першого шпальти вкороченій системи

(10)

є елемент другий рядки, робимо в (10) перестановку рядків і тим самим не від системи (9) переходимо до еквівалентній системі

(11)

що можна записати в матричному вигляді як

. (12)

Отже система (12) отримана з (8) застосуваннямелемен-тарной матриці перестановок

Далі до системи (11) треба застосувати другий крок винятку звичайного методу Гаусса. Це еквівалентно множенню системи (11) на елементарну нижню трикутну матрицю

Через війну одержимо систему

(13)

чи

(14)

Заключний крок прямого ходу методу Гаусса полягає у заміні останнього рівняння системи (14) рівнянням

що еквівалентно множенню (13) на елементарну нижню трикутну матрицю

Отже, для розглянутої прикладу процес винятку Гаусса з головного елемента по стовпцю записується в

вигляді

(15)

За побудовою матриця

(16)

є верхньої трикутною матрицею з одиничної головною діагоналлю.

Відмінність від зазвичайного методу Гаусса у тому, що на посадісомножителей в (16) поруч із елементарними трикутними матрицями можуть бути присутні елементарні матриці перестановок .

Покажемо ще, що з (16) слід розкладання

PA=LU

, (17)

де L -нижня трикутна матриця, має зворотний,P - матриця перестановок.

І тому знайдемо матрицю

(18)

По властивості 2) матриця виходить з матриці перестановкою другої і третьої рядків,

Матриця відповідно до властивості 3) виходить з перестановкою другого і третього шпальт

тобто. -нижня трикутна матриця, має зворотний.

З (18), враховуючи рівність , одержимо

(19)

Звідси й з (16) видно, що

де зазначено . ОскількиР-матрица перестановок іL-нижняя трикутна матриця, властивість (17) доведено. Воно означає, що метод Гаусса з головного елемента по стовпцю еквівалентний звичайному методу Гаусса, застосованому до матриці РА, тобто. до системи, отриманою з вихідної системи перестановкою деяких рівнянь.

Загальний висновок. Результат, отриманий раніше дуже приватного прикладу, справедливий у разі загальної системи рівнянь (1).

Як-от, метод Гаусса з головного елемента по стовпцю можна записати як

(20)

де - елементарні матриці перестановок такі, що

і -елементарні нижні трикутні матриці.

Звідси, використовуючи співвідношенняперестановочности, аналогічні (19), можна показати, що метод Гаусса з головного елемента еквівалентний звичайному методу Гаусса, застосованому до системи

PAx=Pf,

(21)

де Р - деяка матриця перестановок.

Теоретичне обгрунтування методу Гаусса з головного елемента міститься у наступній теоремі.

ТЕОРЕМА 1.

Коли на те існує матрицяперестано-

>вок Р така, що матриця РА має які від нуля кутові ми-

нори.

Доказ в п.4.

СЛІДСТВО.

Коли на те існує матрицяпрестана-

>вок Р така, що справедливе розкладання

РА=LU,

(22)

де L- нижня трикутна матриця із чудовими від нуля діагональними елементами і U- верхня трикутна матриця з одиничної головною діагоналлю. І тут на вирішення системи (1) можна використовувати метод Гаусса з головного елемента.

4. Доказ теореми 1.Докажем теорему індукцією за кількістю >m -порядку матриці А.

Нехай >m=2, тобто.

Коли на те твердження теореми виконується при >Р=Е, де Є - одинична матриця другого порядку. Якщо , то ,т.к. У цьому у матриці

все кутові мінори відмінні від нуля.

Нехай твердження теореми вірно для будь-яких квадратних матриць порядку >m-1. Покажемо, що його правильно, і .для матриць порядкуm. Ра>зобьем матрицю А порядкуm на блоки

де

Досить розглянути два випадку : і . У першому випадку за припущенням індукції існує матриця перестановок порядку >m-1 така, що є які від нуля кутові мінори. Тоді для матриці перестановок

маємо

причому . Тим самим було все кутові мінори матриці РА відмінні від нуля.

Розглянемо другий випадок, коли .Т.к. , знайдеться хоча б тільки відмінний від нуля мінор порядку >m-1 матриці А, отриманий викреслюванням останнього шпальти від будь-якої рядки. Нехай, наприклад,

де .

>Переставляя в матриці А рядки з номерами l і >m, одержимо матрицю , що має кутовий мінор порядкуm-1 має вигляд

і від (23) лише перестановкою рядків. Отже, цей мінор не нульовий і ми дійшли розглянутому вище випадку.

Теорему доведено.

>ВЫЧИСЛЕНИЕОПРЕДЕЛИТЕЛЯ МЕТОДОМГАУССА З ВИБОРОМ ГОЛОВНОГОЭЛЕМЕНТА.

 

 

 

Одночасно з вирішенням системи лінійних алгебраїчних рівнянь

можна визначити визначник матриці А.

нехай у процесі винятку знайденораспожение

тобто. побудовано матриці L U . Тоді

отже, твір діагональнихелементов матриці L (провідних, головнихелементов методу винятку) одноопределителю матриці РА. Оскільки матриці РА й О відрізняються лише перестановкою рядків, визначник матриці РА може відрізнятиметься від визначників матриці Та лише знаком.

Як-от,

Отже, для обчислення означника треба зазначити, скільки перестановок було у процесісключения.

Якщо матриця Авироджена, то, при використанні метод Гаусса з головного елемента по стовпцю на деякому кроці винятку До все елементи якого шпальти, які перебувають нижче головною діагоналі і ній, виявляться рівниминулю.При цьому подальше виняток стає неможливим і яскрава програма повинна видати інформацію у тому, що визначник матриці нульовий.

ЗВЕРНЕННЯМАТРИЦ.

Перебування матриці, зворотної матриці А ,еквивалентно рішенню матричного рівняння

(1)

де Є - одинична матриця, X - бажана квадратна матриця.

>Уравнение (1) можна записати як системи рівнянь

(2)

де

Можна зауважити, що систему (2) розпадається наm незалежних систем рівнянь з і тієї ж матрицею А , але з різними правими частинами. Ці системи мають

вид ( фіксуємо j ) :

(3)

де з вектора - шпальти дорівнює одиниціj-та компонента і рівні нулю інші компоненти.

Наприклад, для матриці другого порядку система (2) розпадається на дві незалежні системи:

> систем (3) використовується метод Гаусса ( звичайний чи з головного елемента).

Розглянемо застосування методу Гаусса без вибору головного елемента. Оскільки всі системи (3) мають те ж матрицю А , цілком вистачило раз зробити прямий хід методу Гаусса, тобто. отримати розкладанняA=LU і запам'ятати матриці L і U .

Зворотний хід здійснюється вирішенням систем рівнянь

з трикутними матрицями L U.

При здійсненні зворотного ходу можна скоротити кількість дій, приймаючи до уваги спеціальний вид правих частин системи (4).

Запишемо докладніше першіj-1 рівнянь системи (4):

З огляду наневирожденность матриці L ( тобто.

звідси отримуємо

У цьому решта рівняння системи (4) мають вигляд

Звідси послідовно перебувають невідомі по формулам:

Можна показати, що це спільне число дій множення і розподілу, необхідне звернення матриці зазначеним способом, порядку . Тим самим було звернення матриці вимагає ненабагато більше часу, ніж вирішення системи рівнянь.

МЕТОДПРОГОНКИ.

Система рівнянь визначення коефіцієнтівсплайна є окреме питання систем лінійних алгебраїчних рівнянь

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

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

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

Тобто. матрицю А можна записати

Ідея методупрогонки ось у чому. Рішення системи (1) шукається як

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

>Виведем формули для обчислення З (3) можна отримати роботу

Підставляючи наявні висловлювання для в рівняння (>1),приходим при до рівнянню Останнє рівняння буде виконано якщо коефіцієнти вибрати такими, щоб висловлювання на квадратних дужках зверталися до нуль.

Як-от, досить покласти Для відшукання всіх досить буде задати

Ці початкові значення знаходимо з вимоги еквівалентності умови (3) при тобто. умови , долю першому з рівнянь (2).

Отже, отримуємо

(5)

Перебування коефіцієнтів по формулам (4), (5) називається прямий прогонкою. Потому, якпрогоночние коефіцієнти знайдено, рішеннясистеми (1), (2) перебувають розслідування щодорекуррентной формулі (3), починаючи з Спочатку рахунку за цієї формули потрібно знати , що визначається з рівнянь

І одно

.

Перебування по формулам

(6)

називається зворотної прогонкою. Алгоритм рішення системи (1), (2) визначається формулами (4)-(6) називається методомпрогонки.

Методпрогонки можнапременять, якщознаменатели висловів (4), (6) необрщаются в нуль.

Покажемо, що з можливість застосування методпрогонки досить зажадати, щоб коефіцієнти системи (1), (2) задовольняли умовам

(8)

Спочатку доведемо по індукції, за сприятливих умов (7), (8) модуліпрогоночних коефіцієнтів вищими за одиниці. Відповідно до (5), (8) маємо .Предположим,что для деякого і доведемо, що

Насамперед для будь-яких двох комплексних чисел і доведемо нерівність

З нерівності трикутника маємо

Звідки

Повернімося тепер до доведенню , якщо . Відповідно до маємо оцінку

а, використовуючи (7) , отримуємо

тобто.знаменатели висловів (4) не звертаються до нуль.

Понад те

Отже,

Далі, враховуючи другий з умов (8) і хіба що доведене нерівність , маємо

тобто. не звертається до нуль і знаменник у натуральному вираженні для .

Аналогічного висновку можна прийти у разі, коли (7), (8) замінюються умовами

Отже, за виконанні умов (7), (8) (як і і умов (9), (10)) система (1), (2) еквівалентна системі (4)-(6). Ці умови гарантують існування й одиничність рішення системи (1), (2) і можливість перебування цього заходу методомпрогонки.

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

Справді, хай у формулі (6) при замість обчислена величина

Тоді ось на чому кроці обчислень, тобто. при

замість

одержимо величину і похибка дорівнюватиме

Звідси отримуємо, що ,тобто. похибка зростає.

Підрахуємо число арифметичних дій, виконуваних під час вирішення завдання (1), (2) методомпрогонки.

По формулам (4), що реалізовані з допомогою шести арифметичних дій, обчислення виробляються раз, за такою формулою (6) виконується 5 арифметичних дій, нарешті за такою формулою (3), що вимагає усього дві дії, обчислення здійснюються раз. Отже в методіпрогонки всього витрачається

арифметичних дій, тобто. число дій зростає лінійно щодо числа невідомих

За позитивного рішення ж довільній системи лінійних алгебраїчних рівнянь методомГаусcа число дій пропорційно кубу числа невідомих.

>ВЫЧИСЛЕНИЕСОБСТВЕННЫХЗНАЧЕНИЙ ІСОБСТВЕННЫХВЕКТОРОВМАТРИЦ.

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

, (1)

і відшукання цих нетривіальних рішень.

Тут -квадратна матриця порядкуm , - невідомий вектор - стовпець.

З курсу алгебри відомо, щонетривиальное рішення системи

Страница 1 из 3 | Следующая страница

Схожі реферати:

Навігація