Решение систем линейных уравнений методом ортогонализации

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

Пусть исходная система имеет вид:

a11x1+a12x2+…+a1nxn  + a1n+1 = 0 a21x1+a22x2+…+a2nxn  + a2n+1 = 0          … an1x1+an2x2+…+annxn  + ann+1 = 0

Левую часть каждого уравнения системы можно рассматривать как скалярное произведение двух векторов: a_i (a_i1, a_i2, …, a_in, a_in+1) и x (x₁, x₂, …, x_n, 1). Таким образом, решение системы сводится к построению вектора x, ортогонального к каждому вектору a_i:

(a_i, x) = 0 для i =1, 2, …, n

Напомним некоторые понятия теории векторов.

Скалярным произведением двух векторов называется сумма произведений соответствующих координат этих векторов:

(x, y) = x₁ ∙ y₁ + x₂ ∙ y₂ + … + x_n ∙ y_n

Вектор u называется ортогональным вектору x, если их скалярное произведение равно 0:

(x, u) = x₁ u₁ + x₂ ∙ u₂ + … + x_n ∙ u_n = 0

Система векторов называется ортогональной, если в ней каждая пара векторов ортогональна.

Такая система векторов является ортогональным базисом n-мерного векторного пространства.

Нормой (длиной) вектора называют квадратный корень из скалярного произведения вектора на себя:

Базис называется ортонормированным, если каждая пара векторов в нем ортогональна, и норма каждого вектора равна 1:

1) (b_i, b_j ) = 0, i ≠ j, i = 1, 2, …, n

2) (b_i, b_j) = 1, i = j, i = 1, 2, …, n

Так как число координат в векторах, образованных коэффициентами системы уравнений, равно n+1, то имеем n+1- мерное пространство. Для построения базиса данного пространства необходимо добавить к системе векторов (a₁, a₂, …, a_n) линейно независимый от них вектор a_n+1 = (0, 0, …,0, 1). (Так как он будет соответствовать в ортогональном базисе вектору x, то его последняя координата должна быть равна 1). В векторном n+1 – мерном пространстве будем строить ортонормированный базис b₁, b₂, …, b_n+1. Для этого достаточно строить некоторый ортогональный базис u₁, u₂, …, u_n+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)

Так как по задаче требуется найти только x₁, x₂, то из данного вектора выберем только первые две координаты. В результате имеем: x₁ = 1, x₂ = 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