Численные решения СЛАУ.


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

Пусть задана система линейных уравнений Ax=U с плотной матрицей, элементы которой хранятся в оперативной памяти.

 

 

Переходим к системе (исключения х1)

Эта операция равносильна умножению Ax=U слева на матрицу

 

где pi1= i=2,3…n A1 x= U1à Ax= U

aij(1)= aij- aij

Следующий переход к системе (исключения х2)

Это исключения равносильно умножению A1 x= U 1 слева на матрицу Р2:

где pi2= i=3,4…n aij(2)= aij(1) - a2j(1)

A1 x= U1=> A1х = U1àP2P1Ax= P2P1 U

Продолжая этот процесс и так далее, мы придем к легко решаемой системе уравнений с треугольной матрицей An-1х =Un-1

 

 

An-1 =

 

An-1- верхняя треугольная матрица. Здесь An-1х=Un-1=> =Pn-1Pn-2Ax= Pn-1Pn-2 U, так что A =(Pn-1Pn-2 …P1)-1 An-1х

 

P Q

       
   

 


A = *

 

Где матрица P- нижняя треугольная, а Q- верхняя треугольная. Решение по методу Гаусса сводится к разложению A на произведение двух треугольных матриц. Одна из них

P~ с единицами по главной диагонали и на верхнюю треугольную

 

Q~

 

Заметим, что

det A=det P*det Q= a11 a22(1) a33(2)… ann(n-1)

Если представления матрицы A в виде PQ найдены, то решение системы Ax=U сводится к решению двух треугольных систем уравнений.

Py= U ↓ (y)

Ax=U=>PQx=U=>

Qx= y ↑ (x)

Решения по методу Гаусса сводится фактически к решению системы Py= U ↓

При прямом ходе, а затем к решению системы Qx= y ↑ при обратном ходе.

Разложение матрицы на две треугольные матрицы называется процессом факторизации (триангуляция) матрицы, т.е. представление матрицы в виде A=PQ.

После вычисления прямого хода мы получаем матрицу An-1= Q

Метод Холецкого, прогонки приводят к факторизации матрицы A.

Метод Холецкого.

Пусть дана невырожденная матрица размером N*N (det A≠0) Представим её в виде произведения

A=BC (1) A~(aij) B~(bij) C~(cij)

 

 

k>i

bik=0, когда k>i

ckj=0 при k>j cjj =1

Из (1) следует

aij= bik cki

Преобразуем эту сумму двумя способами

aij= bik cki= bik cki+ bii cij+ bik cki= bik cki+ bii cij

 

aij= bik ckj= bik ckj+ bij cjj+ bik ckj= bik ckj+ bij cjjà bij cjj= aij- bik ckj

Отсюда находим

bij= i ≥ j b11=a11 cjj=1

cjj= при I < j

Матрицы B и C найдены, тогда Ax= BCx=U

By=U ↓ (y) прямой ход

 


Cx=y ↑ (x) обратный ход

 


Лекция 8

Метод прогонки.

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

Пусть требуется найти решение следующей системы трехточенных уравнений.

 

Или в векторной форме

A (2)

 
 


A=

                   
         


По методу Гаусса A= * = *

Факторизация ленточных матриц, т.е. разложение их на произведение двух треугольных матриц A=PQ

(нижней и верхней) треугольных матриц может быть произведено так, что P и Q также будут ленточными матрицами.

Перейдем к следующей системе (3)

yj=pj+1yj+1+qj+1 (3)

Где pj+1 и qj+1 неизвестные числа

           
     


u0- p1u1 =q1

u1- p2u2 =q2 =

u0- p1u1 =q3

 

 

Числа pj и qj можно искать из системы (1), т.к.

yj-1=pjyj+qj (4)

Подставляя (4) в систему (1) получим

-aj(pj yj+ qj)+cj yj-bj yj+1=fj

(cj-aj pj)yj=bj yj+1 +(fj+ aj qj)

(5)

Сравнивая (5) с(3) получим

(6)

Из 1го крайнего условия

y0 =p1y1+q1

=> (7)

 

Из 2го крайнего условия

yn-1= pnyn+qn

-an yn-1+cnyn=fn (8)

Теперь с помощью (3) получим


Проверка метода прогонки на устойчивость.

Поскольку вычисления pj и qj производятся по рекуррентным формулам, то в зависимости от элементов матрицы A: ai, bi, ci, то неизбежны ошибки округления при вычислении по рекуррентным формулам pj и qj. Эти ошибки могут быстро возрастать и сделать вычисления непригодными. Поведение ошибки dpj+1 можно проследить, положив её приближённо равной дифференциалу функции.

Имеем

(9)

Прогонка будет устойчивой, если и (10)

Тогда dpj+1 <dpj

Эти неравенства (10) будут выполнены, если, например, положить, что коэффициент матрицы A удовлетворяют следующие условия

0≤ aj≤bj

cj≥ aj+bj (11) j=

0<

В самом деле

, отсюда

<

Вообще, проверяется pj+1≤ 1 для j=1,n-1

При этих условиях при вычислении pj+1 накопление ошибки не происходит. Аналогично из равенств

;

<dqj

Т.к. при тех же условиях (11) нарастания погрешностей при вычислении q j+1 не происходит.

 

Лекция 9



Дата добавления: 2016-07-27; просмотров: 2080;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.019 сек.