Метод ньютона (касательных). 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Метод ньютона (касательных).



Если уравнение имеет корень и непрерывную производную на отрезке , то функцию можно выбрать в виде

.

В результате задача определения корня уравнения сводится к отысканию корня уравнения

. (1)

Итерационный метод решения уравнения, использующий преобразование исходного уравнения к виду (1), называют методом Ньютона. При этом получим следующую рекуррентную формулу

(2)

Построим график функции . Уравнение касательной в точке будет иметь вид

Найдём точку пересечения этой касательной с осью у. Так как при , то

Тот же результат получим из соотношения (2) при . Следовательно, первое приближение корня можно найти и геометрически с помощью касательной к графику функции в точке . Аналогичным путём можно построить второе и последующие приближение. Отсюда название метод касательных.

Следует отметить, что при сходимость алгоритма метода Ньютона будет наблюдаться при любых начальных приближениях в интервалах .

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

,

где m, M – некоторые положительные константы, для которых

,

для всех .

Приведём алгоритм решения уравнения методом Ньютона в виде блок – схемы:

 

 

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

В заключение следует отметить, что при решении нелинейных уравнений

 

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

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

Пусть задана система линейных уравнений 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-04-19; просмотров: 379; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 52.90.50.252 (0.076 с.)