Реферат: Численные методы

ЛЕКЦИЯ №1

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

Погрешности, возникающиепри решении задач, бывают двух видов:

 1)абсолютная

 />/>p- p /> , где    p  — точноезначение, p — не точное.

 2)относительная

 />

                                   Эмпирические данные:

Погрешности                      Случайные                        Ошибки

измерительного                     помехи                            набора

прибора

1) Нахождение нулейфункции;

2) Системы линейныхи нелинейных уравнений;

3) Приближениефункции. Интерполяция. Экстраполяция.

4) Решениедифференциальных уравнений.

5) Расчетсобственных значений и собственных векторов  матриц.

НАХОЖДЕНИЕ НУЛЕЙ ФУНКЦИИ

Общая постановка задачи

Дана некоторая функцияf(х). Необходимо найти хотя бы одно значение х, при котором f(х)=0.

Этапы:

1) Отделение корней.

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

содержится единственныйкорень функции.

2) Уточнение корня припомощи одного из численных методов на каждом из выбранных отрезков.

Нуль функции – точкапересечения графика функции с осью Ох.

Непрерывность f(х) вточке х0:

/>

Производная функции:    f' =/>/>

Физический смысл: f'(х0)- скорость

Геометрический смысл: f'(х0)-тангенс угланаклонной касательной к графику функции, проведенной в данной точке.

Если функциядифференцируема в точке, то она непрерывна. Обратное не верно.

Предел функции в точке: />

 />x: | x-x0| </> 

/>ε >0 />(ε)

  | f(x) – A|< ε

         Градиент функции– это вектор.

/>

Геометрический смысл:показывает направление локального возрастания функции в данной точке .

/>

1) Наблюдаем сменузнака функции.

2) Исследуем функциюна монотонность.

Теорема №1: если функция f(x) непрерывна на отрезке [a, b] и в концахотрезка принимает значения разных знаков, то на этом отрезке функция имеет хотябы один корень.

f(x) /> C[a, b]

f(a) * f(b)< 0 → />/>/>[a,b]  f(/>)=0

Теорема№2:если функция непрерывна и монотонна на отрезке и  вконцах отрезка принимает значения разных знаков, то на этом отрезке существуеттолько единственный корень функции.

/>/>f(x) />C[a,b], f    (    ) и f(a) * f(b) < 0→/>/>/>[a, b]  f(/>) = 0

МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ

/>

Дано: f(x) непрерывна на[a,b], на [a,b] существует динственный корень f(x)=0, ε

1) Делим отрезок пополам.Получаем точку

с= (b + a)/2.

Если f(a) * f(c) < 0, тоb:=c.

Если f(b) * f(c) < 0, то а:=с

2) Продолжаем делить [a,b] на 2, пока|b-a| > ε, где ε- заданная точность.

ЛЕКЦИЯ №2

МЕТОД ХОРД

Дано: 1) f(x) /> C''[a, b]

      2) f(a) * f(b) < 0

      3) f'(x) и f''(x) знакопостоянна на отрезке [a, b].

      4) ε, чтобыполучить f(x)=0

/>    

  1) f(b)                                                          2)

                                               f'(x) >

0                                                        f'(x)> 0

                                               f''(x) >

0                                                      f''(x) < 0

/>           f(a)   a                                x

/>     3)                                                                  4)

                                                   f'(x)

<0                                                    f'(x) <0                                                                      

                                                   f''(x)

<0                                                    f''(x) > 0   

/> (2.1)

x1(x1,f(x1))

/>

b – неподвижный конец отрезка.

Для случаев 1), 3)

/>

Для случаев 2), 4)

/>

Можем ввести некоторую с:

/>  (2.2)

/>   (2.3)

Алгоритм:

1) Вычисляемнеподвижный конец отрезка секущих по формуле(2.3)

2) Находим первоеприближение к корню по формуле (2.1)

3) Находим первоеприближение к корню по формуле (2.2) до тех пор, пока модуль разности двухпоследних приближений не станет меньше заданной точности. В этом случае,значением корня является последнее приближение.

МЕТОД КАСАТЕЛЬНЫХ

Дано: 1) f(x)/> C''[a, b];

2) f(a)*f(b) < 0;

3) f'(x) и f''(x) знакопостоянны на [a, b];

4) ε, чтобы решить уравнение f(x)=0

/> 

                                                                                              />

                                                                                                 т. х0

                                                                                    y=f(x0)+f'(x0)(x-x0) –

                        уравнениекасательной

                    a        x2           x1       b

y=f(b)+f’(b)*(x-b)

(x1,0): 0= f(b)+ f’(b)(x1-b)

x1=/>

x2=/>

xn+1=/>      (2.4)

Второйподход (метод Ньютона):

/>-приближение

0 = f(/>) = f(xn+hn) ≈ f(xn)+f'(xn)*hn

x0=/> начальноеприближение                    (2.5)

Алгоритм:

1) По формуле (2.5)находим первое приближение к корню х0(начальное)

2) По формуле (2.4)находим последующее приближение к корню до тех пор, пока модуль разности двухпоследних приближений не станет заданной точности. В этом случае корень равенпоследнему приближению.

МЕТОД ИТЕРАЦИЙ

Дано: 1) f(x)/>C''[a,b]

 2)f(a)*f(b)<0

 3)f'(x) знакопостоянна

 4)ε, f(x)=0

Уравнение f(x)=0 заменяется уравнением вида x=φ(x)

φ(x)=x-f(x)*C       (2.6)

/>                                              Пока|xn+1-xn|<ε

                                                     φ' >0

                                                     Cтроим последователь /> 

                                                     Выбираем />

                                                     Находим значение функции

                                                       x2= φ(x1), x3= φ(x2)

                                                      xn+1= φ(xn)                   (2.7)

Точка ε, для которойвыполняется ε=f(ε),называется неподвижной точкой метода итераций. Очевидно, что эта точка являетсякорнем уравнения f(x)=0.

φ(ε)/> ε -f(x)* ε

0 />f(ε)*C

f(ε) />0

Достаточное условие: длятого, чтобы метод итераций сходился достаточно чтобы:

1) φ(x)/> (2.8) — Функция является непрерывной идифференцируемой на [a,b].

2) φ(x) значения  /> - является необходимымусловием

3) |φ(x)|<1 для всех />

Константа С вформуле(2.6) подбирается таким образом, чтобы функция

φ(x) удовлетворяла условиям сходимостиметода итераций.

Скорость сходимостиметода Ньютона (касательных) выше сходимости метода секущих (хорд).

ЛЕКЦИЯ №3

МЕТОДЫ РЕШЕНИЯ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Общий вид алгебраическогоуравнения:

а0хn+ а1хn+1+…+ аn-1х+an=0, a0/>0                          (3.1)

n=1: а0х+a1=0, x=/>

n=2: а0х2+a1x+a2=0, x1,2=/>

Алгебраическое уравнение n- степени имеет ровно n корней.

Теорема Виета(обобщенная):

xn+/>xn-1+…+/>x+/>=0

x1+x2+…+xn=-/>;                                       (3.2)

x1x2+x1x3+…+xn-1xn=/>;

x1x2x3…xn=(-1)/>;

Пусть все корни уравнения(3.1) действительны, различны и удовлетворяют соотношениям:

|x1|>>|x2|>>…>>|xn|                                               (3.3)

Преобразуем:

/>x1(1+/>+…+/>)=/> />  x1=-/>;                                          (3.4)

Подставим(3.4): х2=-/> продолжая получим общуюформулу

хk=-/>, k=1,n                                                                  (3.5)

Корни уравнения,удовлетворяющие соотношения(3.3), называются отдельными. Задача состоит в том,чтобы по исходному уравнению построить такое уравнение, корни которого будутотделены.

yi=-xim

b0yn+ b1yn-1+…+ bn-1y+bn=0                                                      (3.6)

|x1|>|x2|>…>|xn|     

Решив уравнение (3.6),корни которого являются отдельными, получим уравнения y1…yn 

/>, i=2,n

Значит    |yi-1|>>|xi|                                                                        

МЕТОД ЛОБАЧЕВСКОГО

Для отделения корней Лобачевскийпредложил метод квадратирования -  способ построения по исходному уравнениюнового уравнения, кони которого связаны с корнями исходного следующим образом:

yi=-xi2                                                                 (3.7)

Процедура выполнениямногократна, пока не достигнем серьёзной разницы модуля разности корней

b0(m)yn+ b1(m)yn-1+…+ bn-1(m)y+bn(m)=0                                        (3.8)

Пустьуравнение (3.8) получено в результате m-го шага квадрирования.

m=1            b0(1)=a02,  b1(1)=a12=2 a0a2

bk(1)=ak2-2ak-1ak+1+2ak-2ak+2….,k=0,n

При полученииbk коэффициента, которыйрассчитывается как квадрат соответствующего коэффициента ak минус удвоенноепроизведение соседних коэффициентов с ak<sub/>плюс удвоенноепроизведение следующей пары соседей, чередуя знаки, пока в число соседнихкоэффициентов не попадут а0и аn.

/>m>1b0(m)=(b0(m-1))2,  b1(m)=( b1(m-1))2-2b0(m-1)b2(m-1)                (3.9)

bk(m)=(b0(m-1))2-2bk-1(m-1)bk-1(m-1)+2bk-2(m-1)bk+2(m-1)

Критерийостановки:  bk(m)≈( b0(m-1))2,        k=0,n                    (3.10)

Получимкорень: yi(m)=-xi2/>,   i=1,n                                          (3.11)

(3.11)-связь корней,полученных на m-шаге процесса квадрирования скорнями исходного уравнения.

yi на m-шаге: />,отсюда

                        /> ,  i=1,n                                  (3.12)

/>Знак xi определяется путем подстановки в исходное уравнение. Те коэффициенты,которые будут отвечать за наличие комплексных корней, имеют следующий признак:один или несколько коэффициентов в ходе процесса квадрирования ведут себянеправильно (все остальные коэффициенты →к квадратам предыдущих, анеправильные →к квадратам предыдущих могут менять знак).

Признак наличиякратных корней: одинили несколько коэффициентов → к половине квадрата коэффициентапредыдущего шага.

МЕТОДЫ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

СЛАУ

Методы решения СЛАУделятся на точные и приближенные. К точным методам относятся метод Гаусса,метод Крамера, метод обратной матрицы .

Существуют приближенныеметоды: метод итераций, Зейделя и т.д.

Общий вид СЛАУ:

/>                     (3.13)

Сколько переменныхстолько и ограничений на них.

/>                   пересечение прямых (точка)

/>    пересечение плоскостей (прямая)   

/>       точка пересечения трех плоскостей

Т.о. геометрический смыслрешения СЛАУ – точка пересечения гиперплоскостей в n-мерном пространстве.

Матрица :/>=А;     B=/>;   X=/>;

Cn*k*Dk*m=Zn*m, An*n*Bn*1=Xn*1/> AX=B                           (3.14)

ЛЕКЦИЯ №4

МЕТОД ГАУССА

Метод имеет прямой иобратный ход. Будем рассматривать процедуру прямого хода метода с выборомглавного элемента. Главный элемент – максимальный по модулю элемент матрицы,выбранный на заданном множестве строк  и столбцов.

1 шаг: Выбираем в матрицеА максимальный элемент по всем строкам и столбцам. Путем перестановки строк истолбцов ставим этот элемент на место а11. Теперь а11-главный элемент.

А→А1→А2→…→Аn

Аn должна будет содержать ниже главнойдиагонали все нули.

/> , j =1,n ;   b1 =b1/a11

Получим систему вида />

/> , i=2,n ,   j=1,n

/>  Получим А' х=В' и систему

/>

Пусть а221– максимальный по модулю элемент матрицы А1 по строкам i≥2 и столбцам j≥2. Если это не так, тодобиваемся этого путем перестановки строк и столбцов.

А2:   />

В2:  b12=b11;  b22=b21/a221; bi2=bi1-b22-b22ai21

Пусть акк+1максимальный по модулю элемент матрицы Ак, i≥k, j≥k.

/>

Пусть на некотором шаге k<n элемент />=0,матрица Вк имеет ∞ множество решений. Причем корни х1,…хкявляются зависимыми, а корни хк+1,….xn – независимые.

Если хотя бы один элементbik  при i≥k+1 ¹ 0, то решения у системы нет.

Если была полученаматрица Аn, то система имеет единственноерешение.

Начинается обратный ходметода Гаусса.

Определитель: det A=/>

det A=/>=a11a22-a12a21

Минор Hij элемента матрицы aij представляет собой определитель,полученный из матрицы А путем вычеркивания i cтроки и   jстолбца.

Алгебраическое дополнениеАij элемента аij называется число, равное

 Аij=(-1)i+j*Mij    

/>

Способывычисления определителей

1. Привестиопределитель к треугольному виду (ниже главной диагонали все элементы=0).Достичь этого можно путем вычитания (сложения) строк определителя, умноженныхна некоторое число. При перестановки строк/столбцов знак определителя меняетсяна противоположный. Определитель треугольного вида равен произведению элементовглавной диагонали.

2. Рекуррентныйспособ основан на том, что определитель равен сумме произведений элементовстроки/столбца на их алгебраические дополнения. Т.о. задача вычисленияопределителя n-го порядка сводится к вычислению n определителей n-1 порядка.

Наиболее целесообразнораскладывать определитель по той строке/столбцу, которая содержит максимальноеколичество нулей. Алгебраическое дополнение 0-го элемента можно не вычислять.

Пусть дана системауравнений вида Ах=В

Если определитель А=0, тосистема может решений не иметь, либо иметь бесконечное множество решений.

Если определитель А≠0,то корни системы могут быть найдены следующим образом.

Пусть Ак-матрица,полученная из матрицы А путем замен к-го столбца на матрицу-столбец В. Тогдарешение />.

Пусть дана система Ах=В иdetA≠0.

Умножим обе части системына А-1:

А-1*Ах=А-1*В→х=А-1*В

Способы нахожденияобратной матрицы:

1.  Способ основан на методе Гаусса.

Записать матрицу А, арядом с ней единичную матрицу. Выполняя элементарные преобразования матрицы А,параллельно выполнять те же преобразования над единичной матрицей. Как толькоматрица А превратилась в единичную на месте исходной единичной матрицы будетобратная к матрице А.

2.  Через алгебраические дополнения.

Составить матрицу алгебраическихдополнений, в которой на месте aij элементов будут находиться Aij.

Разделить каждый элементматрицы алгебраических дополнений на detA.

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