Метод ортогонализации является одним из прямых методов, что позволяет получить более компактный алгоритм.
Пусть исходная система имеет вид:
a11x1+a12x2+…+a1nxn + a1n+1 = 0 a21x1+a22x2+…+a2nxn + a2n+1 = 0 … an1x1+an2x2+…+annxn + ann+1 = 0 |
Левую часть каждого уравнения системы можно рассматривать как скалярное произведение двух векторов: ai (ai1, ai2, …, ain, ain+1) и x (x1, x2, …, xn, 1). Таким образом, решение системы сводится к построению вектора x, ортогонального к каждому вектору ai:
(ai, x) = 0 для i =1, 2, …, n
Напомним некоторые понятия теории векторов.
Скалярным произведением двух векторов называется сумма произведений соответствующих координат этих векторов:
(x, y) = x1 ∙ y1 + x2 ∙ y2 + … + xn ∙ yn
Вектор u называется ортогональным вектору x, если их скалярное произведение равно 0:
(x, u) = x1 u1 + x2 ∙ u2 + … + xn ∙ un = 0
Система векторов называется ортогональной, если в ней каждая пара векторов ортогональна.
Такая система векторов является ортогональным базисом n-мерного векторного пространства.
Нормой (длиной) вектора называют квадратный корень из скалярного произведения вектора на себя:
|
|
Базис называется ортонормированным, если каждая пара векторов в нем ортогональна, и норма каждого вектора равна 1:
1) (bi, bj ) = 0, i ≠ j, i = 1, 2, …, n
2) (bi, bj) = 1, i = j, i = 1, 2, …, n
Так как число координат в векторах, образованных коэффициентами системы уравнений, равно n+1, то имеем n+1- мерное пространство. Для построения базиса данного пространства необходимо добавить к системе векторов (a1, a2, …, an) линейно независимый от них вектор an+1 = (0, 0, …,0, 1). (Так как он будет соответствовать в ортогональном базисе вектору x, то его последняя координата должна быть равна 1). В векторном n+1 – мерном пространстве будем строить ортонормированный базис b1, b2, …, bn+1. Для этого достаточно строить некоторый ортогональный базис u1, u2, …, un+1, а затем нормировать его.
Алгоритм построения ортонормированного базиса:
a) u1 = a1;
b) ;
c) Искомый вектор x равен:
Пример. Решить систему уравнений:
x1 +0∙x2 = 1 x1 +x2 = 2 |
Проверим явное решение системы x1 = 1; x2 = 1. Для этого построим систему векторов по коэффициентам уравнений: a1 (1, 0, -1); a2 (1, 1, -2). Добавим к этим векторам вектор a3 (0, 0, 1).
Построим ортонормированный базис:
a)
b)
c)
Так как по задаче требуется найти только x1, x2, то из данного вектора выберем только первые две координаты. В результате имеем: x1 = 1, x2 = 1. Как видно, этот результат совпадает с явным решением системы, что доказывает верность предложенного алгоритма.
Задание
Систему трех линейных уравнений с тремя неизвестными
a11x1 +a12x2+a13x3 = b1 a21x1 +a22x2+a23x3 = b2 a31x1 + a32x2 +a33x3 = b3 |
решить различными способами:
|
|
0) определить, есть ли решение данной системы, вычислив определитель матрицы коэффициентов при неизвестных;
1) найти решение системы методом простой итерации с точностью ε = 10 –4;
2) найти решение системы методом Зейделя с точностью ε = 10 –4 (приведение системы к нормальному виду выполнить на ЭВМ);
3) найти решение системы методом ортогонализации (построение ортонормированного базиса выполнить на ЭВМ).
Провести анализ полученных результатов каждым из методов и сделать вывод об их эффективности для данной системы линейных уравнений.
Задание взять из таблицы. Все указанные задания должны быть выполнены в одной программе.
Таблица.
Вариант | i | ai1 | ai2 | ai3 | bi |
1. | 1 2 3 | 0,21 0,30 0,60 | -0,45 0,25 -0,35 | -0,20 0,43 -0,25 | 1,91 0,32 1,83 |
2. | 1 2 3 | -3 0,5 0,5 | 0,5 -6 0,5 | 0,5 0,5 -3 | -56,5 -100 -210 |
3. | 1 2 3 | 0,45 -0,01 -0,35 | -0,94 0,34 0,05 | -0,15 0,06 0,63 | -0,15 0,31 0,37 |
4. | 1 2 3 | 0,63 0,15 0,03 | 0,05 0,10 0,34 | 0,15 0,71 0,10 | 0,34 0,42 0,32 |
5. | 1 2 3 | -0,20 -0,30 1,20 | 1,60 0,10 -0,20 | -0,10 -1,50 0,30 | 0,30 0,40 -0,60 |
6. | 1 2 3 | 0,30 -0,10 0,05 | 1,20 -0,20 0,34 | -0,20 1,60 0,10 | -0,60 0,30 0,32 |
7. | 1 2 3 | 0,20 0,58 0,05 | 0,44 -0,29 0,34 | 0,81 0,05 0,10 | 0,74 0,02 0,32 |
8. | 1 2 3 | 6,36 7,42 5,77 | 11,75 19,03 7,48 | 10 11,75 6,36 | -41,40 -49,49 -27,67 |
9. | 1 2 3 | -9,11 7,61 -4,64 | 1,02 6,25 1,13 | -0,73 -2,32 -8,88 | -1,25 2,33 -3,75 |
10. | 1 2 3 | -9,11 7,61 -4,64 | 1,02 6,25 1,13 | -0,73 -2,32 -8,88 | -1,25 2,33 -3,75 |
11. | 1 2 3 | 1,02 6,25 1,13 | -0,73 -2,32 -8,88 | -9,11 7,62 4,64 | -1,25 2,33 -3,75 |
12. | 1 2 3 | 0,06 0,99 1,01 | 0,92 0,01 0,02 | 0,03 0,07 0,99 | -0,82 0,66 -0,98 |
13. | 1 2 3 | 0,10 0,04 0,91 | -0,07 -0,99 1,04 | -0,96 -0,85 0,19 | -2,04 -3,73 -1,67 |
14. | 1 2 3 | 0,62 0,03 0,97 | 0,81 -1,11 0,02 | 0,77 -1,08 -1,08 | -8,18 0,08 0,06 |
15. | 1 2 3 | 0,63 0,90 0,13 | -0,37 0,99 -0,95 | 1,76 0,05 0,69 | -9,29 0,12 0,69 |
16. | 1 2 3 | 0,98 0,16 9,74 | 0,88 -0,44 -10 | -0,24 -0,88 1,71 | 1,36 -1,27 -5,31 |
17. | 1 2 3 | 0,21 0,98 0,87 | -0,94 -0,19 0,87 | -0,94 0,93 -0,14 | -0,25 0,23 0,33 |
18. | 1 2 3 | 3,43 74,4 3,34 | 4,07 1,84 94,3 | -106 -1,85 1,02 | 46,8 -26,5 92,3 |
19. | 1 2 3 | 0,66 1,54 1,42 | 0,44 0,74 1,42 | 0,22 1,54 0,86 | -0,58 -0,32 0,83 |
20. | 1 2 3 | 0,78 0,02 0,12 | -0,02 -0,86 0,44 | -0,12 0,04 -0,72 | 0,56 0,77 1,01 |