Реферат: Численные методы
ЛЕКЦИЯ №1
Численные методыпредставляют собой набор алгоритмов, позволяющих получать приближенное(численное) решение математических задач.
Погрешности, возникающиепри решении задач, бывают двух видов:
1)абсолютная
/>/>p- p /> , где p — точноезначение, p — не точное.
2)относительная
/>
Эмпирические данные:
/> /> /> /> /> /> /> /> /> /> /> <td/> /> /> />Погрешности Случайные Ошибки
измерительного помехи набора
прибора
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.
Транспонировать матрицуалгебраических дополнений, т.е. поменять местами элементы, симметричныеотносительно главной диагонали.