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

Рассмотрим систему m линейных уравнений с n неизвестными:

ìa   x + a   x     + ... + a   x     = b  
ï 11 +       +   + 1n   n   =  
ïa21x1 a22 x2   ... a2n xn   b2  
í......................                              
ï                                        
ïa   x + a m2 x + ... + a mn x n = b  
î m1 1                      

Ее можно записать в матричном виде A x = B, где

æ a a ... a ö æ b ö æ x ö  
ç   1n ÷ ç ÷ ç ÷  
ç a21 a22 ... a2n ÷ ç b2 ÷ ç x2 ÷  
A =ç ...       ÷ b =ç ... ÷ x =ç ... ÷  
ç       ÷ ç ÷ ç ÷  
             
ç   am 2     ÷ ç   ÷ ç   ÷  
èam1   amn ø èbm ø è xm ø  

Решить СЛУ –значит найти набор таких чисел

уравнения в верные равенства.

СЛУ совместна, если она имеет хотя бы одно решение.

СЛУ несовместна (противоречива), если она не имеет решения.

Совместная СЛУ определенна, если она имеет единственное решение и неопределенна, если более одного решения.

СЛУ имеет единственное решение, если ранг матрицы A равен рангу расширенной матрицы (A|b): rang(A) = rang(A|b).

СЛУ имеет единственное решение, если rang(A) = n и бесконечно много решений, если rang(A) < n.

Если матрица A – квадратная и det(A)¹0, то она называется невырожденной.

СЛУ с n неизвестными, имеющими невырожденную матрицу A, совместна и имеет единственное решение.


 
«Минусы»
· Требуют приведения к определенному виду

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

Обратной матрицей по отношению к матрицеAназывается такая матрицаA-1,чтоA A-

1=A-1 A = E.

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

Квадратная матрица симметрична, если A=AT.

Все численные методы решения СЛУ можно разделить на прямые, итерационные и вероятностные.

Прямые методы дают решение системы за конечное число арифметических операций.

Например, метод Крамера (метод определителей),

метод Гаусса (метод последовательного исключения неизвестных).

  «Плюсы» «Минусы»
· Просты · Достаточно громоздкие вычисления
· Универсальны  
· Не требуют приведения к  
определенному виду  

Итерационные методы дают решение системы как предел последовательностиприближений, вычисляемых по единообразной схеме.

Например, метод простой итерации, метод Зейделя.

Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №1 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №2 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №3 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №3 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №3 - открытая онлайн библиотека

«Плюсы»

· Требуют мало места в памяти · Самоисправляющиеся методы

Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №1 - открытая онлайн библиотека

Вероятностные методы носят общее название–методы Монте-Карло.

Пусть получено решение СЛУ: ~ . Рассматривается вектор невязки         ~ . Если      
        e  
x e = b - Ax  

велико, то где-то допущена ошибка, если e мало, то ошибка отсутствует.

Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №7 - открытая онлайн библиотека

Метод Гаусса.

Метод Гаусса относится к точным методам, однако вычислительная ошибка присутствует всегда (ошибка округления и, возможно, ошибка исходных данных). Рассмотрим систему m линейных уравнений с n неизвестными:

ìa   x + a   x     + ... + a   x     = b  
ï 11 +       +   + 1n   n   =  
ïa21x1 a22 x2 ... a2n xn   b2  
í......................                              
ï                                        
ïa   x + a m2 x + ... + a mn x n = b  
î m1 1                     n  

Алгоритм состоит из двух этапов.

I. Прямой ход – приведение матрицы к треугольному виду (сверху вниз):

ìx + a¢ x + ... + x n =  
ï         1n        
ï   x + ... +   x n =  
            2n        
í......................                      
ï                                
ï                     xn = bn¢  
î                      

II. Обратный ход–определение неизвестных(снизу вверх).

Ручные вычисления по схеме единственного деления оформляют в виде таблицы с контролем вычислений, для чего в таблицу включены

· столбец контрольных сумм S,

· столбец сточных сумм S.

Контроль в прямом ходе:

· После внесения коэффициентов при неизвестных и свободных членов исходной системы находят контрольные суммы (суммы коэффициентов и свободных членов по строкам) и вносят их в столбец S.

· Далее, выполняя преобразования, над контрольными суммами производятся те же преобразования, что и над свободными членами.

· После выполнения каждого преобразования находят строчную сумму результатов и помещают ее в столбец S.

· При отсутствии вычислительных ошибок числа в столбцах S и S должны практически совпадать.

Контроль в обратном ходе:

При безошибочном выполнении вычислений в столбце S должны быть на единицу больше соответствующих значений неизвестных из столбца свободных членов Рассмотрим примеры решения СЛУ методом Гаусса

Разделы x1   x2 x3 св чл сумма S
    3,25 14,52 -1,32 367,58 384,03  
    32,02 -4,36 5,73 516,91 550,3  
А   7,21 11,92 -41,46 -886,32 -908,65  
               
    4,4677 -0,4062 113,1015 118,1631 118,163
    -147,4158 18,7365 -3104,6000 -3233,2825 -3233,2793
    -20,2921 -38,5313 -1701,7818 -1760,606 -1760,6052
               
А1     -0,1271 21,0602 21,9331 21,9331
      -41,1104 -1274,4261 -1315,5373 -1315,5365
               
А2       31,0001 32,0001 32,0001
               
        31,0001 32,0001  
В     25,0003 26,0003  
    13,9999  

Решение систем линейных алгебраических уравнений. Требования к сходимости итерационного процесса.

Первая половина в билете №9.

Функцию r(x,y), определяющую расстояние между точками x и y множества X назовем метрикой, если

1) r(x,y)³0

2) r(x,y)=0 • x=y

3) r(x,y)= r(y,x)

4) r(x,y)£ r(x,z)+ r(z,y).

Множество X с введенной метрикой r назовем метрическим пространством. Последовательность точек метрического пространства называется фундаментальной,

если ("e > 0)($N )("m, n > N )[r(xm , xn ) < e].

Пространство называется полным, если в нем любая фундаментальная последовательность сходится.

Отображение F пространства E в себя называется сжимающим, если

($a, 0 < a <1)("x, y Ï E)[r(F(x), F( y)) £ a r(x, y)]

x – неподвижная точка, если F(x)=x.

Оценка расстояния между неподвижной точкой и приближением x(k) производится следующим образом:

r(x, x(k ))£   a k r(x(0), x(k ))или r(x, x(k ))£   a r(x(k -1) , x(k ) ).  
1 -a 1 -a  
       

Таким образом, чтобы погрешность вычислений была меньше наперед заданного числа

ε, достаточно потребовать r(x(k -1) , x(k ) )£ e 1 -a .  
   
              a  
Рассмотрим 3 типа метрики.      
Пусть x(x1,x2,…,xn) и y(y1,y2,…,yn) – две точки n-мерного пространства.  
I. r1 (x, y) = max   xi - yi   Максимальная из сумм модулей коэффициентов при неизвестных в  
     
  1£i£n                
               
правой части системы, взятых по строкам, должна быть меньше единицы:  
  n            
a1 = max1£i£n å aij <1            

Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №8 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №9 - открытая онлайн библиотека

j=1

n

II. r21 (x, y) = å xi - yi Максимальная из сумм модулей коэффициентов при неизвестных

Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №10 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №10 - открытая онлайн библиотека

i=1

в правой части системы, взятых по столбцам, должна быть меньше единицы:  
      n                    
a2 = max1£j£n å   aij < 1              
                       
      i=1                    
                               
III. r3 (x, y) =   n - yi )2Корень квадратный из суммы квадратов коэффициентов при  
  å(xi  
              i=1              
неизвестных   в правой части системы, должен быть меньше единицы:  
                           
    n n                    
a3=å åaij2¹1<1          
    i=1 j =1                    

Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №12 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №13 - открытая онлайн библиотека

СЛУ преобразуется таким образом, чтобы по одной из метрик выполнялось α < 1.


                                                   
ìx   = a     x + a     x     + ... + a   x       + b      
ï 1                   1n   n          
ïx2 = a21x1 + a22 x2   + ... + a2n xn   + b2    
í......................                                        
ï                                                    
ïx n = a   x + a m2 x + ... + a mn x n =   b n  
î     m1 1                            

При этом СЛУ задает отображение, которое при α < 1 будет сжимающим. Значит, взяв любую точку в качестве начального приближения, получим последовательность точек, которая будет сходиться к неподвижной точке; это точка и будет решением системы. Чтобы привести СЛУ к итерационному виду нужно:

1) с помощью равносильных преобразований привести систему к виду с преобладающими диагональными коэффициентами (по абсолютной величине);

2) разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным единице.

Если для этой системы α < 1, то система задает сжимающее отображение.

11. Оценка погрешности метода простой итерации. x=Bx+d;

Пусть ||B||<1, имеем:

x*=Bx*+d;

x(k)=Bx(k-1)+d;

x*=x(k)+B(x*–x(k-1));

Вычтем из каждой части x(k-1):

x*–x(k-1)=x(k)–x(k-1)+B(x*–x(k-1));

||x*–x(k-1)||≤

||x(k)–x(k-1)||+||B||-||x*–x(k-1)||;

||x*–x(k-1)||-(1–||B||)≤

||x(k)–x(k-1)||;

||x*–x(k-1)||≤

||x(k)–x(k-1)||/(1–||B||);

Кроме того:

||x*–x(k)||≤||B||-||x*–x(k-1)||;

||x*–x(k)||≤(||B||/(1–||B||))-||x(k)–x(k-1)||; (1)–Разность между точным решением иk-ымприближением.

Пусть требуется найти решение с точностью ε. Из (1) имеем:

(||B||/(1–||B||))-||x(k)–x(k-1)||<ε;

Достаточно выполнение условия:

||x(k)–x(k-1)||≤((1–||B||)-ε)/||B||;–критерий выхода.

Метод Зейделя

При решении СЛУ методом простой итерации каждый шаг итерационного процесса состоит в переходе от уже имеющегося приближения значений неизвестных к новому приближению.

Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении значений yi учитываются уже полученные значения y1, y2,…,yi-

1.

I. Условие α<1 является достаточным для сходимости итерационного процесса метода Зейделя. Причем метод Зейделя обеспечивает более быструю сходимость, чем метод простой итерации.

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

program slu_zejdel1;

{ *** с использованием евклидовой метрики *** } var p,b,x1,x2,x3,y1,y2,y3,a,e: real;

N: integer;

begin

write('Введите x1, x2, x3 : '); readln(x1,x2,x3);

write('Введите A, E : '); readln(a,e);

b:=e*(1-a)/a;

N:=0; {число итераций}

repeat

N:=N+1;

y1:= 0.1362*x2-0.1790*x3+16.1433;

y2:=-0.2238*y1+0.0909*x3+25.3154;

y3:= 0.1739*y1+0.2875*y2+21.3777;

p:=sqrt(sqr(x1-y1)+sqr(x2-y2)+sqr(x3-y3));

x1:=y1; x2:=y2; x3:=y3;

until p<=b;

writeln('x1 = ',x1:8:6);

writeln('x2 = ',x2:8:6);

writeln('x3 = ',x3:8:6);

writeln('Число итераций - N = ',N);

readln

end.

Введите x1, x2, x3 : 0 0 0

Введите A, E : 0.2218 0.0001

x1 = 13.999370

x2 = 25.000219

x3 = 30.999753

Число итераций - N=6

Как видно из примера, по сравнению с методом итераций решение получено за меньшее количество шагов.

II. Рассмотрим практическую схему преобразования исходной СЛУ, гарантирующую сходимость метода Зейделя.

Пусть система записана в матричной форме: Ax=b.

Умножим левую и правую части слева на матрицу AT: ATAx= AT b.

Обозначим : ATA=C, AT b=d.

Преобразованная система станет иметь вид: Cx=d. Такую систему называют нормальной:

· матрица C является симметричной;

· все элементы главной диагонали матрицы C положительны. Нормальную систему легко привести к виду:

xi =åaij x j + b j , (i = 1,2,¼, n) , где ai = - cij ( j ¹ i) и bi = di .            
cii              
    j ¹i                     cii            
Вычислительные формулы имеют вид:                          
ì   n                                        
ïy1 = åa1 j x j + b1                                      
ï   j =1                                        
                                           
ï     n                                      
ïy2 = a21 y1 + åa2 j x j + b2                                  
ï     j =1                                      
ï                                            
ï...                                            
í   i-1 n                                      
ï                                        
=åaij y j +åaij x j + bi                                  
ïyi                                  
ï   j =1 j =i                                      
                                           
ï...                                            
ï   n-1                                        
ïyn =åanj y j + ann xn + bn                                  
î                                            
ï   j =1                                        
Рассмотрим на примере.                                
  æ 3,25 14,52   -1,32 ö æ 367,58 ö   æ 3,25   32,02   7,21 ö  
  ç   - 4,36     ÷ ç       ÷   ç         - 4,36     ÷  
A = ç 32,02   5,73 ÷ b = ç 516,91 ÷ AT = ç 14,52   11,92 ÷  
  ç 7,21 11,92 - 41,46 ÷ ç - 886,32 ÷   ç -1,32 5,73 - 41,46 ÷  
  è ø è ø   è ø  
    æ 1087,827 - 6,474 -119,742 ö           æ   11355,726 ö    
    ç - 6,474     - 538,3524 ÷   D =       ç - 7481,4004 ÷    
C = AT A = ç 371,9264 ÷   AT b = ç ÷    
    ç -119,742 - 538,3524 1753,5069 ÷           ç   39223,5159 ÷    
    è ø           è   ø    

После деления на диагональные элементы получим:

æ - 0,0060 - 0,1101ö æ 10,4389 ö  
ç - 0,0174   -1,4475 ÷ ç   ÷  
a = ç ÷ b = ç - 20,1153÷  
ç - 0,0683 - 0,3070 ÷ ç 22,3686 ÷  
è ø è ø  

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, r1 (x, y) = max xi - yi ).

Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №14 - открытая онлайн библиотека Решение систем линейных алгебраических уравнений. прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема - №14 - открытая онлайн библиотека

1£i£n

program slu_zejdel2;

var x1,y1,x2,y2,x3,y3,e,a,b,c: real;

N: integer;

begin

write('Введите X1, X2, X3 - '); readln(x1,x2,x3); write('Введите погрешность Е - '); readln(e); N:=0; {число итераций}

repeat

N:=N+1;

y1:= 0.0060*x2+0.1101*x3+10.4389;

y2:= 0.0174*y1+1.4475*x3-20.1153;

y3:= 0.0683*y1+0.3070*y2+22.3686;

a:=abs(y1-x1); b:=abs(y2-x2); c:=abs(y3-x3);

if a<b then a:=b;

if a<c then a:=c;

x1:=y1; x2:=y2; x3:=y3;

until a<=e;

writeln('X1 = ',x1:11:8);

writeln('X2 = ',x2:11:8);

writeln('X3 = ',x3:11:8);

writeln('Число итераций - N = ',N);

readln

end.

Введите X1, X2, X3 - 0 0 0

Введите погрешность Е - .0001

X1 = 14.00204110

X2 = 25.00128107

X3 = 31.00033269

Число итераций - N = 18