Зміст. I Теоретична частина 1. Введення ................................................. ................... 3
2.
Чисельні методи ................................................ .. 6
1) Матричний метод ........................................ 6
2)
Метод Крамера ............................................. 9
3)
Метод Гауса ... ... ... ... ............................... 12
4) Ітерації для лінійних систем .... ... .. ... .. 17
a) Ітерація Якобі .. ... ... ... ... ... ... ... ... .. 18
b) Ітерація Гаусса - Зейделя .. ... ... ... ... 20
II Практична частина 1) Матричний метод ........................................ 22
2)
Метод Крамера ............................................. 24
3)
Метод Гауса ... ... ........................................ 26
4) Лістинг програми. ... ... ... ... ... ... ... ... ... .28
III Користь запровадження розрахунків. ... ... ... ... ... ... ... ... ... ... ... ... .65
IV Література ... ... ... .. ........................................... .................... 66
I. Теоретична частина. Введення. Лінійна алгебра - частина алгебри, що вивчає
векторні (лінійні) простору і їх підпростору, лінійні відображення (оператори), лінійні, Білінійні, і квадратичні
функції на векторних просторах.
Лінійна
алгебра,
чисельні методи - розділ обчислювальної математики, присвячений математичному опису і дослідженню
процесів чисельного рішення задач лінійної алгебри.
Серед завдань лінійної алгебри найбільше значення мають дві: рішення
системи лінійних алгебраїчних рівнянь визначення власних значень і власних
векторів матриці. Інші часто зустрічаються завдання: звернення матриці, обчислення визначника і т.д.
Будь-який чисельний метод лінійної алгебри можна розглядати як деяку послідовність виконання арифметичних операцій над елементами вхідних даних. Якщо за будь-яких вхідних даних чисельний метод дозволяє знайти рішення задачі за кінцеве число арифметичних операцій, то
такий метод називається
прямим. У протилежному випадку чисельний метод називається
ітераційним. Прямі методи - це такі, як метод Гаусса, метод облямівки, метод поповнення, метод спряжених градієнтів та ін Ітераційні методи - це метод простої ітерації, метод обертань, метод змінних напрямків, метод релаксації і ін Тут будуть розглядатися матричний метод, метод Гаусса і
метод Крамера.
У даній роботі будуть розглянуті чисельні методи в електронних
таблицях Excel і програмі
MathCAD, Microsoft Visual
Basic.
MathCAD. Програма
MathCAD за своїм призначенням дозволяє моделювати в
електронному документі науково-технічні, а також
економічні розрахунки у формі, досить близькою до загальноприйнятих ручним
розрахунками. Це спрощує
складання програми розрахунку,
автоматизує перерахунок і побудова графічних ілюстрацій подібно електронних таблиць Excel,
документування результатів як в текстовому редакторі Word.
Програма Mathcad відома за легкість, з якою
математичні рівняння,
текст, і графіка можуть бути об'єднані в одному документі. Крім
того, обчислювальні здатності Mathcad поширюються від складання стовпця чисел до вирішення інтегралів і похідних, рішення систем рівнянь і більше.
Перевагою MathCAD є також наявність в його складі електронних книг. Одна з них -
підручник по самій програмі, інші -
довідник з різних розділів математики, фізики, радіоелектроніки та ін
Microsoft Office Excel.
Якщо ж говорити про програму Excel, яка є однією з найбільш відомих в обробці електронних таблиць, то без перебільшення можна стверджувати, що її можливості практично невичерпні.
Обробка тексту,
управління базами даних - програма настільки потужна, що в багатьох випадках перевершує спеціалізовані програми - редактори або програми баз даних. Таке різноманіття функцій може спочатку навіть відлякувати, ніж змусити застосовувати їх на практиці. Але в міру набуття досвіду користувач зможе оцінити майже безмежні можливості Excel.
За всю історію табличних розрахунків із застосуванням
персональних комп'ютерів вимоги користувачів до подібних програм істотно змінилися. Спочатку основний акцент у такій програмі, як, наприклад,
Visi Calc, робився на обчислювальні функції. Сьогодні, положення змінилося. Поряд з інженерними й бухгалтерськими розрахунками
організація і графічне зображення даних набуває все більшого значення. Крім того, різноманіття функцій, пропоноване такою обчислювальною й графічною програмою, не повинне ускладнювати роботу користувача. Програми для
Windows створюють для цього ідеальні передумови.
Останнім часом багато якраз перейшли на використання Windows як свою користувальницького середовища. Як наслідок, багато фірм, що створюють
програмне забезпечення, почали пропонувати велику кількість програм для Windows.
Visual Basic.
Microsoft Visual Basic - це потужна
система програмування, що дозволяє швидко і ефективно створювати додатки для Microsoft Windows. На відміну від Excel та MathCAD це найбільш зручна програма для розв'язання систем лінійних рівнянь. Простий інтерфейс, що дозволяє легко переключатися з проекту форми на сам код програми.
Зручне вікно для коду самої програми:
Чисельні методи. Розв'язність системи лінійних рівнянь. Коли ми говоримо про головну матриці системи лінійних рівнянь, то завжди маємо на увазі квадратну матрицю nXn, тобто матрицю з однаковою кількістю рядків і стовпців. Це важливо.
Якщо, наприклад, кількість рядків (кількість рівнянь у системі) буде менше, ніж кількість стовпців (фактично, кількості невідомих), то система буде невизначеною, тобто ми не зможемо однозначно визначити всі невідомі (вирішити систему).
Але це не єдине обмеження. З векторної алгебри відомо, що система лінійних рівнянь має рішення (однозначне) тоді і тільки тоді, коли її головний визначник не дорівнює нулю: Δ ≠ 0.
Розглянемо
випадок, коли визначник системи дорівнює нулю. Тут можливі два варіанти:
1. Δ = 0 і кожен з додаткових
визначників Δx
i = 0. Це має місце тільки тоді, коли коефіцієнти при невідомих x
i пропорційні, тобто кожне рівняння системи виходить з першого рівняння множенням обох його частин на число k. При цьому система має незліченну безліч рішень.
2. Δ = 0 і хоча б один додатковий визначник Δx
i ≠ 0. Це має місце тільки тоді, коли коефіцієнти при всіх невідомих x
i, пропорційні. При цьому виходить система з суперечливих рівнянь, яка не має рішень.
Матричний метод розв'язання систем лінійних рівнянь. Нехай дана система лінійних рівнянь:
Розглянемо матрицю, складену з коефіцієнтів при невідомих:
Вільні члени і невідомі можна записати у вигляді матриці стовпців:
Тоді, використовуючи правило множення матриць, цю систему рівнянь можна записати так:
або
A · x = b. (1)
Рівність (1) називається матричним рівнянням або системою рівнянь в матричному вигляді.
Матриця А коефіцієнтів при невідомих називається головною
матрицею системи.
Іноді розглядають також розширену матрицю системи, тобто головну матрицю системи, доповнену стовпцем вільних членів, яку записують у наступному вигляді:
Будь-яку лінійну систему рівнянь можна записати в матричному вигляді. Наприклад, нехай дано систему:
Ця система з двох рівнянь з трьома невідомими - x, y,. У вищій математиці можна розглядати системи з дуже великого числа рівнянь з великою кількістю невідомих і тому невідомі прийнято позначати тільки буквою х, але з індексами:
Запишемо цю систему в матричному вигляді:
Тут головна матриця системи:
Розширена матриця буде
мати вигляд:
Рішення матричних рівнянь. Матричні рівняння вирішуються за допомогою зворотних матриць. Рівняння вирішується таким чином. Нехай матриця А - невироджена (D ≠ 0), тоді існує обернена матриця А-1. Помноживши на неї обидві частини матричного рівняння, маємо А-1 (АХ) = А-1В. Використовуючи сочетательних закон множення, перепишемо це рівність у вигляді
(А-1А) Х = А-1В.
Оскільки А-1 А = Е і ЕХ = Х, знаходимо:
Х = А-1В.
Таким чином, щоб вирішити матричне рівняння, потрібно:
1. Знайти обернену матрицю А-1.
2. Знайти добуток оберненої матриці А-1 на матрицю стовпчик вільних членів В, т. е А-1В.
Користуючись визначенням рівних матриць, записати відповідь.
При цьому власне знаходження оберненої матриці -
процес досить трудомісткий і його
програмування навряд чи можна назвати елементарним завданням. Тому на практиці частіше застосовують чисельні методи вирішення систем лінійних рівнянь.
До чисельних методів розв'язання систем лінійних рівнянь відносять такі як: метод Гаусса, метод Крамера, ітеративні методи. У методі Гаусса, наприклад, працюють над розширеною матрицею системи. А в методі Крамера - з
визначниками системи, утвореними за спеціальним правилом.
Метод Крамера. При вирішенні систем лінійних рівнянь за методом Крамера послідовно виконується наступний алгоритм:
1. Записують систему в матричному вигляді (якщо це ще не зроблено).
2. Обчислюють головний визначник системи:
3. Обчислюють всі додаткові
визначники системи:
4. Якщо головний визначник системи не дорівнює нулю, то виконують пункт 5. Інакше розглядають питання про можливість розв'язання даної системи (має незліченну безліч рішень або не має рішень). Знаходять значення всіх невідомих за формулами Крамера для розв'язання системи n лінійних рівнянь з n невідомими, які мають вигляд:
Приклад 1 Вирішити за методом Крамера систему з трьох рівнянь з трьома невідомими:
Рішення Запишемо головний та побічні визначники системи:
Обчислимо ці визначники:
Δ = 3 * 4 * (-4) +7 * (-3) * 5 + (-2) * (-8) * 5-5 * 4 * 5-3 * (-3) * (-8) - 7 * (-2) * (-4) = 48-105 +80-100-72-56 = 128-333 = -205.
Δ1 = -112 + (-45) + (-192) - (-240) -24-168 = -112-45-192 +240-24-168 = 240-541 = -301.
Δ2 = -36-420-280-75 +196-288 = 196-1099 = -903.
Δ3 = -144-147-30-140 +27-168 = -629 +27 = -602.
Головний визначник системи не дорівнює нулю. Знаходимо невідомі за формулами Крамера.
Підставимо знайдені значення визначників у формули Крамера:
x1 = Δ1 / Δ = -301 / (-205) = 1,468292682927 ≈ 1,47;
x2 = Δ2 / Δ = -903 / (-205) = 4,40487804878 ≈ 4,4;
x3 = Δ3 / Δ = -602 / (-205) = 2,936585365854 ≈ 2,93.
Висновок. При вирішенні систем лінійних рівнянь за методом Крамера використовуються формули, в яких беруть участь як головний, так і додаткові визначники системи:
Нагадаємо, що головним
визначником системи називається визначник головною матриці системи, складеної з коефіцієнтів при невідомих:
Якщо в головному визначнику системи замінити по черзі стовпці коефіцієнтів при x
1, x
2, ... x
n на стовпець вільних членів, то отримаємо n додаткових визначників (для кожного з n невідомих):
При цьому важливим є питання про можливість розв'язання даної системи, який вирішується
порівнянням головного і додаткових визначників системи з нулем:
Метод Гауса - прямий і зворотний хід. Розглянемо метод Гаусса. Наприклад, нехай дана розширена матриця деякої системи m лінійних рівнянь cn невідомими:
Будемо вважати, що a
11 ≠ 0 (якщо це не так, то досить переставити першу і деяку іншу рядок розширеної матриці місцями). Проведемо такі елементарні
перетворення:
C
2 - (a
21 / a
11) * C
1, ...
C
m - (a
m1 / a
11) * C
1, тобто Ci-(a
i1 / a
11) * C
1, i = 2, 3, ..., m.
Т. е. від кожного рядка розширеної
матриці (крім першої) віднімаємо перший рядок, помножену на частку від ділення першого елемента цього рядка на діагональний елемент а
11. У результаті отримаємо матрицю:
Тобто перший рядок залишилася без змін, а в стовпці під а
1 1 на всіх місцях опинилися нулі. Звернемо увагу, що перетворення торкнулися всіх елементів рядків, починаючи з другої, всієї розширеної матриці системи.
Тепер наше завдання полягає в тому, щоб отримати нулі під всіма діагональними елементами матриці А - a
ij, де I = j.
Повторимо наші елементарні перетворення, але вже для елемента α
22. C
1 - (a
12 / α
22) * C
2, ...
C
m - (α
m2 / α
22) * C
2, тобто C
i - (α
i2 / α
22) * C
2, i = 3, ..., m.
Т. е. від кожного рядка розширеної матриці (тепер окрім першої і другої) віднімаємо другий рядок, помножену на частку від ділення першого елемента цієї (поточної) рядки на діагональний елемент α
22. Такі перетворення тривають до тих пір, поки матриця не приведеться до верхнє - трикутникове виду. Тобто під головною діагоналлю не виявляться всі нулі:
Згадавши, що кожен рядок являє собою одне з рівнянь лінійної системи рівнянь, легко помітити, що останнім m-е рівняння приймає вигляд:
γ
mn * x
n = δ
m. Звідси легко можна знайти значення першого кореня - x
n = δ
m / γ
mn. Підставивши це значення в попереднє m-1-е рівняння, легко отримаємо значення x
n-перше кореня.
Таким чином, піднімаючись до самого верху зворотним ходом методу Гауса, ми послідовно знайдемо всі корені системи рівнянь.
Приклад 1 Розглянемо систему рівнянь:
Головний визначник даної системи:
Δ = [1 * (-4) * (-2) +2 * 2 * 1 + (-1) * (-1) * (-1)] - [1 * (-4) * (-1) + 2 * (-1) * (-2) +2 * (-1) * 1] = [8 +4-1] - [4 +4-2] = 11-6 = 5,
тобто Δ ≠ 0.
Тобто система визначена і можна вирішити. Вирішимо її за методом Гауса.
Проведемо прямий хід методу Гаусса, виписавши попередньо розширену матрицю системи:
Отримаємо нулі під головною діагоналлю в першому стовпці розширеної матриці. Для отримання нуля в елементі a21 (тобто під діагоналлю в другому рядку матриці) другий рядок матриці перетворимо за формулою C
2 - (a
21 / a
11) * C
1 = C
2 - (2 / 1) * C
1 = C
2 -2 * C
1: Аналогічно робимо і з елементом А31 (тобто під діагоналлю в третьому рядку матриці). Третій рядок матриці перетворимо за формулою C
3 - (a
31 / a
11) * C
1 = C
3 - (-1 / 1) * C
1 = C
3 + C
1: Таким чином, ми отримали нулі під головною діагоналлю в першому стовпці розширеної матриці. Залишилося одержати нуль під головною діагоналлю в другому стовпці матриці, тобто на місце елемента А32. Для цього третій рядок матриці перетворимо за формулою C
3 - (a
32 / a
22) * C
2 = C
3 - (1/-2) * C
2 = C
3 +1 / 2C
2: Таким чином, провівши
прямий хід методу Гаусса, ми отримали розширену матрицю системи, приведену до верхньо-трикутникове увазі:
Ця матриця еквівалентна системі:
Зворотним ходом методу Гауса знайдемо коріння системи. З останнього рівняння знайдемо корінь х
3: -5/2x
3 = 3 / 2,
x
3 = (3 / 2): (-5 / 2) = 3 / 2 * (-2 / 5) = -3 / 5.
Корінь x
3 = -3 / 5 знайдений.
Підставимо його у верхнє (друге) рівняння системи (-2x
2-3x 3 = 1):
-2x
2 -3 (-3 / 5) = 1,
-2x
2 +9 / 5 = 1,
Ітерація для лінійних систем. Спосіб ітерацій дає можливість одержати послідовність наближених значень, що сходяться до точного розв'язку системи, подібно до того, як це робиться для одного рівняння.
Для визначеності обмежимося системою з чотирьох рівнянь із чотирма невідомими (система четвертого порядку), яку запишемо у вигляді:
Дозволимо перше рівняння системи відносно х
1: х
1 = (-a
12 / a
11) х
2-a 13 / a
11 х
3-a 14 / a
11 х
4-a 15 / a
11. Потім дозволимо друге рівняння відносно х
2 і т. д. Тоді систему можна переписати у вигляді:
де α =-a
ik / a
ii, i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.
Система є окремим випадком запису види:
При цьому лінійна
функція L
1 фактично не залежить від х
1. Задамо будь-які початкові значення невідомих (нульові наближення):
х
1 (0), х
2 (0), х
3 (0), х
4 (0). Підставляючи ці значення у праві частини системи (*), отримаємо перші наближення:
Отримані перші наближення можуть бути так само використані для отримання другого, третього і т. д. наближень. Тобто можна записати:
Умови збіжності ітераційного
процесу.
Встановимо умови, виконання яких забезпечить збіжність виходять наближень до істинного (точному) рішенню системи х
1, х
2, х
3, х
4. Не вдаючись у подробиці, скажемо, що для того щоб ітераційний
процес сходився до точного розв'язання, достатньо, щоб всі коефіцієнти системи були
малі порівняно з діагональними.
Цю умову можна сформулювати й більш точно:
Для збіжності процесу ітерацій достатньо, щоб у кожному стовпці сума відносин коефіцієнтів системи до діагональних елементів, узятим з того ж рядка, була строго менше одиниці: Ітерація Якобі. Розглянемо систему лінійних рівнянь:
Рівняння можна записати у вигляді:
Це дозволяє запропонувати наступний ітераційний процес:
або (інший вид запису)
Покажемо, що якщо почати з точки P
0 = (х
1 (0), х
2 (0), х
3 (0), х
4 (0)) = (1, 2, 2), то ітерація (3) сходиться до вирішення (2, 4, 3). Підставимо х
1 =
1, х
2 =
2, х
2 =
2 в праву частину кожного рівняння з (3), щоб отримати нові значення:
Нова точка P
1 = (х
1 (1), х
2 (1), х3
(1), х
4 (1)) = (1.75, 3.375, 3), ближче, ніж P
0. Ітерація, що використовує (3), генерує послідовність точок {P
k}, що сходиться до вирішення (2, 4, 3):
k
| х1 (k)
| х2 (k)
| х3 (k)
|
0
| 1.0
| 2.0
| 2.0
|
1
| 1.75
| 3.375
| 3.0
|
2
| 1.84375
| 3.875
| 3.025
|
3
| 1.9625
| 3.925
| 2.9625
|
4
| 1.990625
| 3.9765625
| 3.0
|
5
| 1.99414063
| 3.9953125
| 3.0009375
|
...
| ...
| ...
| ...
|
15
| 1.99999993
| 3.99999985
| 3.0009375
|
...
| ...
| ...
| ...
|
19
| 2.0
| 4.0
| 3.0
|
Цей процес називається
итерацией Якобі і може використовуватися для вирішення певних типів лінійних систем.
Ітерація Гауса-Зейделя. Процес ітерації Якобі іноді можна модифікувати для прискорення збіжності.
Відзначимо, що ітеративний процес Якобі виробляє три
послідовності - {х
1 (k)}, {х
2 (k)}, {х
3 (k)}, {х
4 (k)}. Здається розумним, що х
1 (k +1) може бути використано замість х
2 (k). Аналогічно х
1 (k +1) і х
2 (k +1) можна використовувати в обчисленні х
3 (k +1). Наприклад, для рівнянь із системи (1) це дасть
такий вигляд ітераційного процесу Гауса-Зейделя, використовує (3 *):
Такий ітераційний процес дасть результати:
k
| х 1 (k)
| х 2 (k)
| х 3 (k)
|
0
| 1.0
| 2.0
| 2.0
|
1
| 1.75
| 3.75
| 2.95
|
2
| 1.95
| 3.96875
| 2.98625
|
3
| 1.995625
| 3.99609375
| 2.99903125
|
...
| ...
| ...
| ...
|
8
| 1.99999983
| 3.99999988
| 2.99999996
|
9
| 1.99999998
| 3.99999999
| 3.0
|
10
| 2.0
| 4.0
| 3.0
|
Т. е. до точного розв'язання ми прийшли вже на 10-му кроці ітерації, а не на 19, як у ітерації Якобі.
Висновок.
1. Спосіб ітерацій дає можливість одержати послідовність наближених значень, що сходяться до точного розв'язку системи. Для цього система приводиться до вигляду (для випадку системи з чотирьох рівнянь):
Ці формули якраз і задають власне ітераційний процес.
2. При цьому щоб ітераційний процес сходився до точного розв'язання, достатньо, щоб всі коефіцієнти системи були малі порівняно з діагональними.
Цю умову можна сформулювати й більш точно:
Для збіжності процесу ітерацій достатньо, щоб у кожному стовпці сума відносин коефіцієнтів системи до діагональних елементів, узятим з того ж рядка, була строго менше одиниці:
3. Слід так само сказати, що ітераційний процес може проводитися як у вигляді ітерації Якобі, так і у вигляді ітерації Гауса-Зейделя. В останньому випадку збіжність ітераційного процесу може істотно поліпшитися.