Шуканий вектор 
Якщо , то система (1) називається погано обумовленою. У цьому випадку похибки коефіцієнтів матриці та правих частин або похибки округлення при розрахунках можуть сильно спотворити рішення.
При вирішенні багатьох завдань права частина системи (1) та коефіцієнти матриці А відомі приблизно. При цьому замість точної системи (1) маємо деяку іншу систему
таку, що
Вважаємо, що величини і d відомі.
Оскільки замість системи (1) маємо систему (2), можемо знайти лише наближене рішення системи (1). Метод побудови наближеного рішення системи (1) має бути стійким до малих змін вихідних даних.
Псевдорішенням системи (1) називається вектор, що мінімізує нев'язку на всьому просторі.
Нехай х 1 – деякий фіксований вектор , який визначається зазвичай постановкою задачі.
Нормальним щодо вектора х 1 рішенням системи (1) називається псевдорішення х 0 з мінімальною нормою, тобто
де F-сукупність всіх псевдорішень системи (1).
Причому 
де ¾компоненти вектора х.
Для будь-якої системи виду (1) нормальне рішення існує і єдине. Завдання знаходження нормального рішення погано обумовленої системи (1) є некоректно поставленим.
Для наближення нормального рішення системи (1) скористаємося методом регуляризації.
Відповідно до зазначеного методу побудуємо функціонал виду, що згладжує.
і знайдемо вектор , що мінімізує цей функціонал. Причому параметр регуляризації a однозначно визначено за умови
де 
.
Вироджені та погано обумовлені системи можуть бути невиразними в рамках заданої точності. Але якщо є інформація про дозвіл системи (1), то замість умови (5) слід використовувати таку умову:
Компоненти 
вектора є рішеннями системи лінійних алгебраїчних рівнянь, яка виходить із умови мінімуму функціоналу (4)
і має вигляд
де Е-одинична матриця,
ермітово сполучена матриця.
Насправді для вибору вектора потрібні додаткові міркування. Якщо їх немає, то вважають =0.
Для =0 систему (7) запишемо у вигляді
де 
Знайдений вектор буде наближеним нормальним рішенням системи (1).
Зупинимося на виборі параметра a. Якщо a=0, то система (7) перетворюється на погано обумовлену систему. Якщо a велике, то система (7) буде добре обумовлена, але регуляризоване рішення не буде близьким до рішення системи (1). Тому занадто велике чи занадто мале, а не придатні.
Зазвичай практично проводять розрахунки з низкою значень параметра a. Наприклад,
Для кожного значення a знаходять елемент , що мінімізує функціонал (4). Як значення параметра регуляризації береться таке число a, для якого з необхідною точністю виконується рівність (5) або (6).
ІІІ. ЗАВДАННЯ
1. Побудувати систему лінійних рівнянь алгебри, що складається з трьох рівнянь з трьома невідомими, з визначником, величина якого має порядок 10 -6 .
2. Побудувати другу систему, аналогічну першій, але має інші вільні члени, відмінні від вільних членів першої системи на величину 0,00006.
3. Вирішити побудовані системи методом регуляризації (вважаючи =0 і d=10 -4) та будь-яким іншим методом (наприклад, методом Гауса).
4. Порівняти отримані результати і зробити висновки щодо застосування використаних методів.
IV. ОФОРМЛЕННЯ ЗВІТУ
У звіті мають бути подані:
1. Назва роботи.
2. Постановка задачі.
3. Опис алгоритму (методу) розв'язання.
4. Текст програми з описом.
5. Результати роботи програми.
БІБЛІОГРАФІЧНИЙ СПИСОК
1. Тихонов А.М., Арсенін В.Я. Методи розв'язання некоректних завдань. - М: Наука, 1979. 286 с.
2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Чисельні методи. - М: БІНОМ. Лабораторія Знань, 2007 636с.
Лабораторна робота № 23
Повернемося знову до СЛАУ Aх = bз квадратною матрицеюА розміру MхN, Яка, на відміну від розглянутого вище "доброго" випадку (див. Розд. 8.г), вимагає спеціального підходу. Звернімо увагу на два схожі типи СЛАУ:
- вироджена система (з нульовим визначником |А|=0);
- погано обумовлена система (визначник А не дорівнює нулюале число обумовленості дуже велике).
Незважаючи на те, що ці типи систем рівнянь суттєво відрізняються один від одного (для першого рішення відсутнє, а для другого існує і єдино), з практичної точки зору обчислювача, між ними багато спільного.
Вироджені СЛАУ
Вироджена система - це система, що описується матрицею з нульовим визначником |A|=0(Сингулярною матрицею). Оскільки деякі рівняння, що входять до такої системи, є лінійною комбінацією інших рівнянь, то фактично сама система є недовизначеною. Неважко збагнути, що, залежно від конкретного виду вектора правої частини ь, існує або безліч рішень, або немає жодного. Перший з варіантів зводиться до побудови нормального псевдорішення (тобто вибору з нескінченної множини рішень такого, яке найбільш близьке до певного, наприклад, нульового вектора). Цей випадок був детально розглянутий у розд. 8.2.2 (див. лістинги 8.11-8.13).
Мал. 8.7. Графічне подання несумісної системи двох рівнянь із сингулярною матрицею
Розглянемо другий випадок, коли СЛАУ Aх = bіз сингулярною квадратною матрицею А не має жодного рішення. Приклад такого завдання (для системи двох рівнянь) проілюстровано рис. 8.7, у верхній частині якого вводяться матриця Ата вектор b, і навіть робиться (невдала, оскільки матриця А сингулярна) спроба вирішити систему з допомогою функції isolve. Графік, що займає основну частину малюнка, показує, що два рівняння, що задають систему, визначають на площині (x0, x1) дві паралельні прямі. Прямі не перетинаються в жодній точці координатної площини, і рішення системи, відповідно, немає.
Примітка
По-перше, зауважимо, що СЛАУ, задана несингулярною квадратною матрицею розміру 2x2, визначає на площині пару прямих, що перетинаються (див. рис. 8.9 нижче). По-друге, варто сказати, що, якби система була спільною, то геометричним зображенням рівнянь були б дві прямі, що збігаються, що описують нескінченну кількість рішень.
Мал. 8.8. Графік перерізів функції нев'язки f(х) = | Ах-b |
Нескладно здогадатися, що в розглянутому сингулярному випадку псевдорішення системи, що мінімізують нев'язку |Ax-b|, буде нескінченно багато, і лежати вони будуть на третій прямій, паралельній двом показаним на рис. 8.7 та розташованої в середині між ними. Це ілюструє рис. 8.8, на якому представлено кілька перерізів функції f(x)= | Аx-b |, Що говорять про наявність сімейства мінімумів однакової глибини. Якщо спробувати використовувати їх знайти вбудовану функцію Minimize, її чисельний метод завжди знаходитиме якусь одну точку згаданої прямої (залежно від початкових умов). Тому для визначення єдиного рішення слід вибрати з усієї множини псевдорішень те, що має найменшу норму. Можна намагатися оформити це багатовимірне завдання мінімізації в Mathcad за допомогою комбінацій вбудованих функцій Minimize, проте більше ефективним способомбуде використання регуляризації (див. нижче) або ортогональних матричних розкладів (див. Розд. 8.3).
Лабораторна робота №3
Вирішення погано обумовлених систем лінійних рівнянь алгебри
Метод регуляризації
Вхідні параметри: n-ціле позитивне число, що дорівнює порядку n системи; а - масив із n х n дійсних чисел, що містить матрицю коефіцієнтів системи; b - масив з n дійсних чисел, що містить стовпець вільних членів системи (b(1) = b 1 , b(2)=b 2, …b(n)=b n) .
Вихідні параметри: х – розв'язання системи; p-кількість ітерацій.
Схема алгоритму наведено малюнку 18.
Текст програми:
procedure regul(N:Integer;a:Tmatr;b:Tvector;var X:Tvector; var p:integer);
var a1,a2:tmatr; b1, b2, x0: tvector; alfa, s1, s: real; max,eps:real; i,j,k,l:integer;
Out_Slau_T(n,a,b);
For I:=1 To n Do (отримання А Т А)
For K:=1 To N Do
Для J: = 1 до N Do S: = S + A * A;
For I:=1 To N Do (отримання А Т В)
For J:=1 To N Do
Begin S: = S + A * B [j];
alfa:=0; (поч-е знач-е альфа)
k:=0; (у ітерацій)
alfa:=alfa+0.01; inc(k); a2:=a1;
for i:=1-N до a2:=a1+alfa; (Отримання А Т А+alfa)
for i:=1 до N b2[i]:=b1[i]+alfa*x0[i]; (Отримання А Т В + alfa)
SIMQ(n,a2,b2,l);
a2:=a1; X: = b2; x0:=X; b2: = b1;
vozm(N,eps,a2,b2);
simq(n,a2,b2,l);
for i:=2 to n do
if abs(b2[i]-X[i])>max then max:=abs(b2[i]-X[i]);
X1 = 1.981 X2 = 0.4735
Рисунок 18 – Схема алгоритму методу регуляризації
Варіанти завдань на вирішення погано обумовлених систем методом регуляризації наведено у таблиці 3.
Метод обертання (Гівенса)
Схема алгоритму наведено малюнку 19.
приклад. Розв'язати систему рівнянь
Текст програми:
PROCEDURE Vrash;
Var I, J, K: Integer; M, L, R: Real; F1: TEXT; Label M1, M2;
Out_Slau_T(nn, aa, b);
for i:=1 to Nn do
For I:=1 To Nn-1 Do Begin
Для K:=I+1 To Nn Do Begin
If (Aa0.0) Then Goto M1; If (Aa0.0) Then Goto M1;
1: M: = Sqrt (Aa * Aa + Aa * Aa);
L:=-1.0*Aa/M;
M2:For J:=1 To Nn Do Begin
R:=M*Aa-L*Aa;
Aa: = L * Aa + M * Aa;
R:=M*Aa-L*Aa;
Aa: = L * Aa + M * Aa;
For I:=Nn Downto 1 Do Begin
Для K:=0 До Nn-I-1 Do Begin M:=M+Aa*Aa; End;
Aa: = (Aa-M) / Aa; End;
для i:=1 до Nn do x[i]:=Aa;End;
Обчислення за програмою призвели до таких результатів:
X1 = 1.981 X2 = 0.4735
Малюнок 19 - Схема алгоритму методу Гівенса (обертання)
Варіанти завдань
Таблиця 3
|
Матриця A |
Матриця A |
||||||
Тема лабораторної роботи №3 контролю знань проілюстрована контрольно – навчальної програмою.
Лабораторна робота №4
Рішення не лінійних рівняньта систем нелінійних рівнянь
Метод простих ітерацій
Порядок виконання лабораторної роботи:
Знайти нульове наближення рішення;
Перетворити систему f(x) = 0 на вигляд х = Ф(х);
Перевірити умову збіжності методу.
Схема алгоритму наведено малюнку 20.
приклад. Вирішити методом простих ітерацій систему
Як нульове наближення виберемо точку х = 1, у = 2.2, z = 2. Перетворимо систему до виду
Текст програми:
PROCEDURE Iteraz;
Var I,J,K,J1: Integer;
X2, X3, Eps: Real;
Eps: = 0.01; X2: = 0.0; K:=1;
For J:=1 To Nn Do Begin
For I:=1 To Nn Do Begin S:=S+Aa*Xx[i]; End;
For J1:=1 To Nn Do Begin Xx:=R; End; X3: = XX;
For I:=1 To Nn Do Begin If (Xx[i]>=X3) Then X3:=Xx[i]; Еnd;
For I:=1 To Nn Do Begin Xx[i]:=Xx[i]/X3; End;
X1: = X3; U:=Abs(X2-X1); U1:=U/Abs(X1);
If (U1> = Eps) Then X2: = X1;
Until ((K>=50)or(U1
Обчислення за програмою призвели до таких результатів:
X(1)= 1.1132 Х(2)= 2.3718 Х(3)= 2.1365
Кількість ітерацій:5
Малюнок 20 - Схема алгоритму методу простих ітерацій
Метод Ньютона
Програму можна використовувати для вирішення систем не вище десятого порядку.
Вхідні параметри: n – число рівнянь системи (збігається з числом невідомих), n£10; х-масив із n дійсних чисел, що містить початкове наближення рішення; f- ім'я зовнішньої процедури f(n, х, у), що обчислює за заданими значеннями х, розташованими в елементах масиву х, поточні значення функції f і розміщує їх в елементах масиву; g - ім'я зовнішньої процедури g(n, x, d), що обчислює за заданими значеннями х із масиву х елементи матриці 
, Яка розміщується в масиві d розмірності n x n; eps – значення умови закінчення ітераційного процесу.
Вихідні параметри: х - масив з n дійсних чисел (він вхідний) містить при виході з підпрограми наближене значення рішення; k-кількість ітерацій.
8.2.3. Вироджені та погано обумовлені системи
Повернемося знову до СЛАУ Aх=b із квадратною матрицею А розміру MхN , яка, на відміну розглянутого вище " хорошого " випадку (див. разд. 8. р), вимагає спеціального підходу. Звернімо увагу на два схожі типи СЛАУ:
- вироджена система (з нульовим визначником | А | = 0);
- погано обумовлена система (визначник А не дорівнює нулю, але кількість обумовленості дуже велика).
Незважаючи на те, що ці типи систем рівнянь суттєво відрізняються один від одного (для першого рішення відсутнє, а для другого існує і єдино), з практичної точки зору обчислювача, між ними багато спільного.
Вироджені СЛАУ
Вироджена система - це система, що описується матрицею з нульовим визначником | A | = 0 (сингулярною матрицею). Оскільки деякі рівняння, що входять до такої системи, є лінійною комбінацією інших рівнянь, то фактично сама система є недовизначеною. Неважко збагнути, що, залежно від конкретного виду вектора правої частини ь, існує або безліч рішень, або немає жодного. Перший з варіантів зводиться до побудови нормального псевдорішення (тобто вибору з нескінченної множини рішень такого, яке найбільш близьке до певного, наприклад, нульового вектора). Цей випадок був детально розглянутий у розд. 8.2.2 (див. лістинги 8.11-8.13).
Мал. 8.7. Графічне подання несумісної системи двох рівнянь із сингулярною матрицею
Розглянемо другий випадок, коли СЛАУ Aх=b із сингулярною квадратною матрицею А немає жодного рішення. Приклад такого завдання (для системи двох рівнянь) проілюстровано рис. 8.7, у верхній частині якого вводяться матриця А і вектор b , а також робиться (невдала, оскільки синхронна матриця А) спроба вирішити систему за допомогою функції isolve . Графік, що займає основну частину малюнка, показує, що два рівняння, що задають систему, визначають на площині (x0, xi) дві паралельні прямі. Прямі не перетинаються в жодній точці координатної площини, і рішення системи, відповідно, немає.
ПРИМІТКА
По-перше, зауважимо, що СЛАУ, задана несингулярною квадратною матрицею розміру 2x2, визначає на площині пару прямих, що перетинаються (див. рис. 8.9 нижче). По-друге, варто сказати, що, якби система була спільною, то геометричним зображенням рівнянь були б дві прямі, що збігаються, що описують нескінченну кількість рішень.
Мал. 8.8. Графік перерізів функції нев'язки f(х) = | Ах-b |
Неважко здогадатися, що у розглянутому сингулярному випадку псевдорішення системи, що мінімізують нев'язку |Ax-b| , буде нескінченно багато, і лежати вони будуть на третій прямій, паралельній двом показаним на рис. 8.7 та розташованої в середині між ними. Це ілюструє рис. 8.8, у якому представлено кілька перерізів функції f(x)= = | Аx-b | , Що говорять про наявність сімейства мінімумів однакової глибини. Якщо спробувати використовувати для їхнього пошуку вбудовану функцію Minimize , її чисельний спосіб завжди знаходитиме якусь одну точку згаданої прямої (залежно від початкових умов). Тому для визначення єдиного рішення слід вибрати з усієї множини псевдорішень те, що має найменшу норму. Можна намагатися оформити це багатовимірне завдання мінімізації в Mathcad за допомогою комбінацій вбудованих функцій Minimize , проте ефективнішим способом буде використання регуляризації (див. нижче) або ортогональних матричних розкладів (див. Розд. 8.3).
Погано обумовлені системи
Погано обумовлена система - це система, у якої визначник А не дорівнює нулю, але кількість обумовленості | А-1 | |А| дуже велике. Незважаючи на те, що погано обумовлені системи мають єдине рішення, практично шукати це рішення найчастіше немає сенсу. Розглянемо властивості погано обумовлених СЛАУ на двох конкретні приклади(Листинг 8.14).
Лістинг 8.14. Рішення двох близьких погано обумовлених СЛАУ
Кожен рядок лістингу 8.14 містить рішення двох дуже близьких погано обумовлених СЛАУ (з однаковою правою частиною ь і матрицями А, що мало відрізняються). Попри близькість, точні рішення цих систем виявляються дуже далекими друг від друга. Треба зауважити, що для системи двох рівнянь точне рішення отримати легко, проте при вирішенні СЛАУ великої розмірності незначні помилки округлення, що неминуче накопичуються при розрахунках (у тому числі і "точним" алгоритмом Гаусса), призводять до величезних похибок результату. Виникає питання: чи має сенс шукати чисельне рішення, якщо заздалегідь відомо, що через нестійкість самого завдання воно може виявитися абсолютно неправильним?
Ще одна міркування, яка змушує шукати спеціальні методи вирішення погано обумовлених СЛАУ (навіть наведеної як приклад у лістингу 8.14 системи двох рівнянь), пов'язане з їхньою фізичною інтерпретацією як результатів експерименту. Якщо спочатку відомо, що вхідні дані отримані з деякою похибкою, то вирішувати погано обумовлені системи не має ніякого сенсу, оскільки малі помилки моделі (матриці А і вектора) призводять до великих помилок рішення. Завдання, що мають такі властивості, називаються некоректними.
Щоб краще зрозуміти причину некоректності, корисно порівняти графічну інтерпретацію добре (рис. 8.9) та погано (рис. 8.10) обумовленої системи двох рівнянь. Рішення системи візуалізується точкою перетину двох прямих ліній, що зображують кожне рівняння.
Мал. 8.9. Графік добре обумовленої системи двох рівнянь
Мал. 8.10. Графік погано обумовленої системи двох рівнянь
З рис. 8.10 видно, що прямі, відповідні погано обумовленої СЛАУ, розташовуються у безпосередній близькості один від одного (майже паралельні). У зв'язку з цим малі помилки розташування кожної з прямих можуть призвести до значних похибок локалізації точки їх перетину (рішення СЛАУ) в протилежність випадку добре обумовленої системи, коли малі похибки в нахилі прямих мало вплинуть на місце точки їх перетину (рис. 8.9).
ПРИМІТКА
Погана обумовленість матриці типова і при реконструкції експериментальних даних, що задаються перевизначеними (неспільними) СЛАУ (наприклад, завдання томографії). Саме такий випадок наведено як приклад у наступному розділі (див. листинг 8.16 нижче).
Метод регуляризації
Для вирішення некоректних завдань, зокрема, вироджених та погано обумовлених СЛАУ, розроблено дуже ефективний прийом, що зветься регуляризацією. В його основі лежить облік додаткової апріорної інформації про структуру рішення (вектор апріорної оцінки хо), яка дуже часто присутня в практичних випадках. У зв'язку з тим, що регуляризація була докладно розглянута в розд. 6.3.3, нагадаємо лише, що рішення СЛАУ Аx=b можна замінити завданням пошуку мінімуму функціонала Тихонова:
Ω (х,λ) = | Ах-b | 2 + λ | х-х0 | 2 . (8.3)
Тут Я - малий позитивний параметр регуляризації, який необхідно підібрати деяким оптимальним способом. Можна показати, що завдання мінімізації функціоналу Тихонова можна, у свою чергу, звести до вирішення іншої СЛАУ:
(А T А+ λ I)-х=АТ В+λ х0, (8.4)
Яка при λ ->0 переходить у вихідну погано обумовлену систему, а при великих x, будучи добре обумовленою, має рішення х0. Очевидно, оптимальним буде деяке проміжне значення А, що встановлює певний компроміс між прийнятною обумовленістю та близькістю до вихідного завдання. Зазначимо, що регуляризаційний підхід зводить некоректне завдання до умовно-коректного (за Тихоновим) завдання пошуку рішення системи (8.4), яке, в силу лінійності завдання, є єдиним і стійким.
Наведемо без зайвих коментарів регуляризоване рішення виродженої системи, яка була представлена на рис. 8.8. Лістинг 8.15 демонструє відшукання розв'язання задачі (8.4), а отримана залежність нев'язки та самого рішення від параметра регуляризації Я показана на рис. 8.11 та 8.12 відповідно. Важливо підкреслити, що рішення вихідної системи і, отже, системи (8.4) при λ =0 не існує.
Лістинг 8.15. Регуляризація виродженої СЛАУ
Заключним кроком регуляризації є вибір оптимального λ . Є, по крайнього заходу, два міркування, з яких, можна вибрати параметр регуляризації, якщо спиратися залежність від нього невязки. У цьому прикладі застосуємо критерій визначення λ , що спирається на підбір норми нев'язки, що дорівнює апріорній оцінці похибок завдання вхідних даних: матриці А і вектора b , тобто величині | δA | + |5λ|. Наприклад, можна вибрати норму нев'язки і, відповідно, параметр λ та рішення х( λ ), які відзначені на рис. 8.11 та 8.12 пунктирами.
ПРИМІТКА 1
Іншим варіантом вибору λ , що не вимагає жодних апріорних міркувань щодо похибок моделі, є так званий квазіоптимальний метод, розглянутий у розд. 6.3.3.
ПРИМІТКА 2
Корисно переконатися в тому, що формула (8.4) у разі лінійного завдання дає той самий результат, що й загальна формула(8.3). Для цього достатньо змінити у лістингу 8.15 останній рядок, що виражає рішення СЛАУ (8.4), на код, що реалізує мінімізацію чисельним методом, як це показано у лістингу 8.16. Розрахунки (які вимагають значно більшого комп'ютерного часу) дають той самий результат, що наведено на рис. 8.11 та 8.12.
ПРИМІТКА 3
Спробуйте в розрахунках лістингів 8.15 та 8.16 взяти іншу, наприклад, більш реалістичну, апріорну оцінку рішення (замість використаного в них нульового вектора х0) та подивитися, як це вплине на результат.
Мал. 8.11. Залежність нев'язки регупяризованого рішення виродженої СЛАУ від параметра А. (продовження лістингу 8.15)
ПРИМІТКА 4
Цікаво також застосувати замість формули (8.3) як функціонал Тихонова іншу залежність: Ω (х,λ ) = |Ах-b|+ λ |х-х0 | . Відповідний приклад розрахунків ви знайдете на компакт-диску.
Мал. 8.12. Регулязоване рішення в залежності від λ (продовження лістингу 8.15)
Лістинг 8.16. Регуляризація СЛАУ за допомогою алгоритму мінімізації (продовження лістингу 8.15) 
Транскрипт
1 6. Вироджені та погано обумовлені СЛАУ 1 6. Вироджені та погано обумовлені СЛАУ Розглянемо тепер два типи СЛАУ (27) з квадратною матрицею A розміру MxM: вироджена система (з нульовим визначником A = 0); погано обумовлена система (визначник A не дорівнює нулю, але кількість обумовленості дуже велика). Незважаючи на те, що ці типи систем рівнянь суттєво відрізняються один від одного (для першого рішення відсутнє, а для другого існує і єдино), з практичної точки зору обчислювача, між ними багато спільного. Вироджена система це система, що описується матрицею з нульовим визначником A = 0 (сингулярною матрицею). Оскільки деякі рівняння, що входять до такої системи, є лінійною комбінацією інших рівнянь, то, фактично, сама система є недовизначеною. Неважко збагнути, що, залежно від конкретного виду вектора правої частини b, існує або безліч рішень, або немає жодного. Розглянемо перший випадок, коли СЛАУ A x=b із сингулярною квадратною матрицею A не має жодного рішення. Цей варіант зводиться до побудови нормального псевдорішення (тобто вибору з нескінченної множини рішень такого, яке найбільш близьке до певного, наприклад, нульового вектора). Наведемо приклад такого завдання (для системи двох рівнянь) A= , b= (37) СЛАУ (37) проілюстровано рис. 19 який показує, що два рівняння, що задають систему, визначають на площині (x 1, x 2) дві паралельні прямі. Прямі не перетинаються ні в
2 2 6. Вироджені та погано обумовлені СЛАУ однією точкою координатної площини, і рішення системи, відповідно, не існує. Зауважимо, що СЛАУ, задана несингулярною квадратною матрицею розміру 2x2, визначає на площині пару прямих, що перетинаються (див. рис нижче). Також варто сказати, що, якби система була спільною, то геометричним зображенням рівнянь були б дві прямі, що збігаються, що описують нескінченну кількість рішень. Мал. 19. Графічне уявлення несумісної СЛАУ Мал. 20. Графік перерізів нев'язки f(x)= A x b залежно від x 1 Нескладно здогадатися, що у аналізованому сингулярному випадку псевдорішень системи (37), що мінімізують нев'язку A x b, буде нескінченно багато, і лежати вони будуть на третій прямій, паралельній двом показаним на рис. 19 та розташованої посередині між ними. Це ілюструє рис. 20, на якому представлено кілька перерізів функції нев'язки f(x) = A x b, які говорять про наявність сімейства мінімумів однакової глибини. Для визначення єдиного рішення слід вибрати з усього безлічі псевдорішень те, що має
3 6. Вироджені та погано зумовлені СЛАУ 3 найменшою нормою. Отже, в сингулярному разі отримання виділеного рішення треба чисельно вирішити багатовимірну завдання мінімізації. Однак, як ми побачимо надалі, ефективнішим способом буде використання регуляризації або ортогональних матричних розкладів (див. 7 і 10 відповідно). Звернемося тепер погано обумовленим системам, тобто. СЛАУ з матрицею A, у якої визначник не дорівнює нулю, але число обумовленості A -1 A велике. Незважаючи на те, що погано обумовлені системи мають єдине рішення, на практиці шукати це рішення найчастіше немає сенсу. Розглянемо властивості погано обумовлених СЛАУ на двох конкретних прикладах дуже близьких погано обумовлених СЛАУ з однаковою правою частиною b і матрицями, що мало відрізняються A і B: A= B=, b=, 3 5. (38) Незважаючи на близькість цих систем, їх точні рішення виявляються дуже далекими друг від друга, саме: y A = , y B = (39) Якщо згадати наявність шуму, тобто. про завжди присутню похибку вхідних даних, то стає зрозумілим, що вирішувати погано обумовлені системи стандартними методами не має ніякого сенсу. Нагадаємо, що завдання, для яких малі помилки моделі (матриці A та вектора b) призводять до великих помилок розв'язання, називаються некоректними. Отже, погано обумовлені СЛАУ є типовим прикладом некоректних завдань. Крім того, слід зазначити, що для системи двох рівнянь точне рішення одержати легко, проте при вирішенні СЛАУ великої розмірності (в тому числі і «точним» алгоритмом)
4 4 6. Вироджені і погано обумовлені СЛАУ Гаусса) навіть незначні помилки округлення, що неминуче накопичуються при розрахунках, призводять до величезних похибок результату. Виникає питання: чи має сенс шукати чисельне рішення, якщо заздалегідь відомо, що через нестійкість самого завдання воно може виявитися абсолютно неправильним? Щоб ще краще зрозуміти причину некоректності, корисно порівняти графічну інтерпретацію добре (рис. 21) та погано (рис. 22) обумовленої системи двох рівнянь. Рішення системи візуалізується точкою перетину двох прямих ліній, що зображують кожне рівняння. Мал. 21. Графік добре обумовленої СЛАУ Мал. 22. Графік погано обумовленої СЛАУ З рис. 22 видно, що прямі, відповідні погано обумовленої СЛАУ, розташовуються у безпосередній близькості один від одного (майже паралельні). У зв'язку з цим, малі помилки в розташуванні кожної з прямих можуть призвести до значних похибок локалізації точки їх перетину (рішення СЛАУ) на противагу випадку добре обумовленої системи, коли малі похибки в нахилі прямих мало вплинуть на місце точки їх перетину (рис. 21). .
5 6. Вироджені та погано обумовлені СЛАУ 5 Зауважимо, що погана обумовленість матриці типова і при реконструкції експериментальних даних, що задаються перевизначеними (несумісними) СЛАУ (наприклад, завдання томографії). Для вирішення некоректних завдань, зокрема, вироджених та погано обумовлених СЛАУ, розроблено дуже ефективний метод, що зветься регуляризацією. В його основі лежить облік додаткової апріорної інформації про структуру рішення, яка дуже часто є у практичних випадках.
10. QR- і SVD-розкладання: «погані» СЛАУ 1 10. QR- і SVD-розкладання: «погані» СЛАУ Серед матричних розкладів особливу роль відіграють ортогональні, що мають властивість збереження норми вектора. Нагадаємо
7. Регуляризация 1 7. Регуляризация Для вирішення некоректних завдань радянським математиком Тихоновим було запропоновано простий, але надзвичайно ефективний метод, званий регуляризацією і заснований на залученні
Приклад: зважування 1 Приклад: зважування Наведемо ще простішу інтерпретацію зворотного завдання, пов'язаного з обробкою результатів будь-якого експерименту, наприклад, зважування предметів двох типів
Тема Чисельні методи лінійної алгебри - - Тема Чисельні методи лінійної алгебри Класифікація Виділяють чотири основні розділи лінійної алгебри: Розв'язання систем лінійних рівнянь алгебри (СЛАУ)
УДК 55 Ісабеков КА Маданбекова ЕЕ ЫГУ їм КТыстанова ПРО НАБЛИЖНЕ РІШЕННЯ ПОГАНО ОБУСЛОВЛЕНИХ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ У цій статті наводяться алгоритми двох методів розв'язання погано
Спеціальний обчислювальний практикум з Андрушевський Микола Матвійович, факультет ВМК МДУ Анотація В основу практикуму покладено докладне вивченняметоду сингулярного розкладання матриць та його застосування
Перевизначені системи лінійних рівнянь Скалько Юрій Іванович Цибулін Іван Шевченко Олександр Перевизначені СЛАУ Перевизначені СЛАУ Розглянемо СЛАУ Ax = b, але у разі коли рівнянь більше,
Системи лінійних рівнянь алгебри Основні поняття Системою лінійних рівнянь алгебри (СЛАУ) називається система виду a a a, a a a, a a a Її можна представити у вигляді матричного рівняння
Ne Іспит з ЛА для бакалаврів економіки в 04-0 уч році, Знайдіть вектор Ne (6 4 ; 6 8) і Ne ДЕМОваріант 0 (x ; y)(у якого Ne і x< 0) такой, чтобы система векторов (x ; y) образовывала бы ортогональный
Рівняння прямої у просторі 1 Пряма як перетин двох площин. Система двох лінійних рівнянь із трьома невідомими. Пряму в просторі можна задати як перетин двох площин. Нехай
ЛЕКЦІЯ 6 СПЕКТРАЛЬНІ ЗАВДАННЯ. Методи спуску На минулій лекції було розглянуто ітераційні методи варіаційного типу. Для системи Au = f, для якої виконується A = A, було введено функціонал Φ(u, u)
11. Лінійна редукція 1 11. Лінійна редукція Завершимо розмову про лінійні зворотні завдання поданням ще одного підходу, званого редукцією. По суті, він дуже близький до регуляризації (у деяких
01 1. Знайдіть загальне та базисне рішення системи рівнянь: x + x + 3x = 26, 2x 12x x = 22, x + 3x + 2x = 20, вибравши як базисні змінні x і x. Відповідь: Якщо як базові змінні вибрати
Демонстраційний варіант 01 1. Знайдіть загальне та базисне рішення системи рівнянь: x + x + 3x = 26, 2x 12x x = 22, x + 3x + 2x = 20, вибравши як базисні змінні x і x. 2. Знайдіть базис системи
Московський державний технічний університет імені НЕ Баумана Факультет «Фундаментальні науки» Кафедра « Математичне моделювання» ÀÍ Êàíàòíèêîâ,
УДК 57.9 Ігрунова С.В., кандидат соціологічних наук, доцент, доцент кафедри « інформаційних систем» Росія, м. Білгород Кічігіна А.К. студент 4 курс, інститут «Інженерних технологій та природничих наук»
6 Методи наближення функцій. Найкраще наближення. Розглянуті в попередньому розділі методи наближення вимагають суворої належності вузлів сіткової функції результуючого інтерполянту. Якщо не вимагати
ЕЛЕМЕНТИ ЛІНІЙНОЇ АЛГЕБРИ ЗАНЯТТЯ МАТРИЦІ І ДІЇ НАД НИМИ Дати визначення матриці Класифікація матриць за розмірами Що таке нульова та поодинока матриці? За яких умов матриці вважаються рівними?
) Поняття СЛАУ) Правило Крамера рішення СЛАУ) Метод Гауса 4) Ранг матриці, теорема Кронекера-Капеллі 5) Рішення СЛАУ зверненням матриць, поняття обумовленості матриць) Поняття СЛАУ О. СЛАУ система
Паралельні обчислення у томографії Алгебраїчні методи обчислювальної томографії. Завдання обчислювальної томографії в дискретної формиЗавдання обчислювальної томографії у дискретній формі. На відміну
ЛЕКЦІЯ 2 ЧИСЛІВЕ РІШЕННЯ СЛАУ Як правило, при вирішенні більшості практичних завдань завдання розв'язання систем лінійних рівнянь алгебри (СЛАУ) зустрічається у вигляді деякої допоміжної підзадачі.
Зразки базових завдань по ЛА Метод Гаусса Визначені системи лінійних рівнянь Розв'яжіть систему лінійних рівнянь методом Гаусса x 6 y 6 8, 6 x 6 y 6 Розв'яжіть систему лінійних рівнянь методом Гаусса 6
Дослідження операцій Визначення Операція - захід, спрямований на досягнення певної мети, що допускає кілька можливостей та їх управління Визначення Дослідження операцій сукупність математичних
Лекція3. 3. Метод Ньютона (дотичних. Задамо деяке початкове наближення [, b] і лінеаризуємо функцію f(в околиці за допомогою відрізка ряду Тейлора f(= f(+ f ")((-. (5 Замість рівняння))
Рівняння прямої та площини Рівняння прямої на площині. Загальне рівнянняпрямий. Ознака паралельності та перпендикулярності прямих. У декартових координатах кожна пряма на площині Oxy визначається
Московський державний технічний університет імені Н.Е. Баумана Факультет «Фундаментальні науки» Кафедра «Математичне моделювання» À.Í. Êàíàòíèêîâ,
Приклади виконання контрольних робіт при заочне навчання Контрольна робота 1 (КР-1) Тема 1. Лінійна алгебра Завдання 1 Необхідно вирішити систему рівнянь, подану у завданні у вигляді Постійні параметри
Московський державний Технічний університетім. н.е. Баумана Факультет Фундаментальні науки Кафедра Вища математика Аналітична геометріяМодуль 1. Матрична алгебра. Векторна алгебра Лекція
Квиток. Матриці, дії над ними. Рівняння параболи в канонічній системі координат. Квиток. Властивості матричних операцій. Взаємне розташуванняпрямий та площині. Кут між ними, умови паралельності
3 ЗМІСТ 1. Цілі та завдання дисципліни 4. Місце дисципліни у структурі ОПОП 4 3. Структура та зміст дисципліни 5 3.1. Структура дисципліни 5 3. Зміст дисципліни 6 4. Перелік навчально-методичного
ПРАКТИЧНІ ЗАНЯТТЯ Заняття НЕОБХІДНІ ТА ДОСТАТНІ УМОВИ БЕЗУМОВНОГО ЕКСТРЕМУМУ Постановка задачі Дана двічі безперервно диференційована функція f (), визначена на множині X R Потрібно досліджувати
Розв'язання задач з алгебри за другий семестр Д.В. Горковець, Ф.Г. Корабльов, В.В. Корабльова 1 Лінійні векторні просториЗавдання 1. Лінійно чи залежні вектори в R 4? a 1 = (4, 5, 2, 6), a 2 = (2, 2, 1,
Федеральне державне освітнє бюджетна установавищого професійної освіти « Фінансовий університетпри Уряді Російської Федерації» (Фінансовий університет) КАФЕДРА «МАТЕМАТИКА»
Xətti ər Rus) üui ithhn sullrı Показати, що вектора;;) ;;) ; ;) утворюють базис вектора і написати лінійну комбінацію вектора Якщо;;) на ці вектори знайти Х з рівняння Показати, що вектора;)
Теорема Кронекер-Капеллі. Рішення СЛАУ методом Гауса. Ранг матриці. Розглянемо прямокутну матрицю, що має m рядків і стовпців: A. m m m Виділимо в цій матриці довільні рядків і стовпців. Елементи
Системи лінійних рівнянь із двома змінними Система рівнянь виду називається системою лінійних рівнянь із двома змінними. Розв'язанням системи рівнянь із двома змінними називається пара значень
ЛІНІЙНА АЛГЕБРА Лекція Пряма і площина в просторі Зміст: Рівняння площини Взаємне розташування площин Векторно-параметричне рівняння прямої Рівняння прямої по двох точках Пряма
САНКТ-ПЕТЕРБУРГСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Факультет прикладної математики процесів управління О. П. ІВАНОВ, Ю. В. ОЛЕМСЬКИЙ ПРАКТИКУМ ЗА КРАМНИЧИМИ МЕТОДами МІНІМІЗАЦІЯ КВАДРАТИЧНОЇ ФУНКЦІЇ Методичні
0 г 6 Праці ФОРА ЧИСЛО ОБумовленості матриці Як показник стійкості при вирішенні прикладних завдань Р Цей, ММ Шумафов Адигейський державний університетМайкоп Число обумовленості матриці
МАТРИЦІ, ВИЗНАЧНИКИ, СИСТЕМИ ЛІНІЙНИХ РІВНЯНЬ Метод окаймляющих мінорів знаходження рангу матриці A = m m m мінора Мінором k порядку k матриці А називається будь-який визначник k-го порядку цієї матриці,
ЛЕКЦІЯ 4 ІТЕРАЦІЙНІ МЕТОДИ РІШЕННЯ СЛАУ Для того щоб зменшити похибку, пов'язану з округленням, вдаються до наступного алгоритму.
1. Лінійні системита матриці 1. Дати визначення множення матриць. Чи комутативна ця операція? Відповідь пояснити. Добуток C матриць A та B визначається як m p m p A B ij = A ik B kj. Операція не комутативна.
МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ ТОМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ СИСТЕМ УПРАВЛІННЯ ТА РАДІОЕЛЕКТРОНІКИ (ТУСУР) Ю.Є. Воскобойніков А.А. Міцель НЕКОРРЕКТНІ ЗАВДАННЯ МАТЕМАТИЧНОГО
Чисельні методи Лінійної Алгебри У розділі «Чисельні методи лінійної алгебри» розглядаються чисельні методи вирішення систем лінійних рівнянь алгебри (СЛАУ) і чисельні методи вирішення завдань
АНАЛІТИЧНА ГЕОМЕТРІЯ 3 ПОТІК Лектор П. В. Голубцов 1.1. Вектор. Список питань до першої частини екзамену 1. Сформулюйте визначення лінійних операцій над векторами. Перелічіть властивості лінійних операцій
Системи лінійних рівнянь алгебри Розглянемо систему m лінійних рівнянь алгебри з невідомими b b () m m m bm Система () називається однорідною якщо всі її вільні члени b b b m рівні
4. Системи лінійних рівнянь. Основні поняття Рівняння називається лінійним якщо він містить невідомі лише у першому ступені і містить творів невідомих тобто. якщо воно має вигляд
Лінійна алгебра Лекція 7 Вектори Введення У математиці є два роди величин скаляри та вектори Скаляр це число, а вектор інтуїтивно розуміється як об'єкт, що має величину та напрямок.
Список питань до іспиту з чисельних методів (28 травня 2018 р.) 0.1 Чисельне інтегрування 1. Перерахувати прийоми обчислення невласних інтегралів. Побудувати квадратурну формулу для обчислення інтегралу
Паралельні обчислення у томографії Метод простої ітерації. Метод якнайшвидшого спуску. Метод ART. Метод SIRT. У методі простої ітерації релаксаційні множники τ k та матриці H k не залежать від номера
Введення до лінійної алгебри Матриці. Визначення. Таблиця m n чисел виду m m n n mn складається з m рядків і n стовпців називається матрицею. Елементи матриці нумеруються аналогічно елементам визначника
ЛЕКЦІЯ 7 ІНТЕРПОЛЯЦІЯ На минулій лекції було розглянуто завдання розв'язання перевизначеної системи. Така система має вигляд: a 11 x 1 + a 1 x + + a 1 x = f 1, (a 1 x 1 + a x + + a x = f, (a 1 x 1 + a x
ПИТАННЯ ТЕОРІЇ I. МАТРИЦІ, ВИЗНАЧНИКИ 1) Дати визначення матриці. Що таке нульова та одинична матриці? За яких умов матриці вважаються рівними? Як виконується операція транспонування? Коли
Лекція 7 ПРИВЕДЕННЯ КРИВОЮ ДРУГОГО ПОРЯДКУ ДО КАНОНІЧНОГО ВИДУ. Перетворення базисів та координат на площині Нехай на площині задані дві прямокутні декартові системикоординат із загальним початком:
Лінійна алгебра Модуль 1. Лінійні та евклідові простори. Лінійні оператори в лінійному просторі Лекція 1.4 Анотація Власні вектори та власні значення лінійного оператора, їх властивості.
УДК. СИНТЕЗ РЕКУРСИВНИХ ЦИФРОВИХ ФІЛЬТРІВ З ІМПУЛЬСНОЇ ХАРАКТЕРИСТИКИ, ВИЗНАЧЕНОЇ ЕЛЕМЕНТАРНОЇ МАТЕМАТИЧНОЇ ФУНКЦІЇ Нікітін Д.А., Ханов В.Х. У сучасному арсеналі методів синтезу рекурсивних
Розділ 8 Функції та графіки Змінні та залежності між ними. Дві величини і називаються прямо пропорційними, якщо їх відношення постійно, тобто якщо =, де постійне число, що не змінюється зі зміною
Метод Гауса (метод виключення невідомих) Дві системи називаються еквівалентними (рівносильними), якщо їх рішення збігаються. До еквівалентної системи можна перейти за допомогою елементарних перетворень
