Численные методы

Выбираем

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

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, a00 (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 a0 a2

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

При получении bk коэффициента , который рассчитывается как квадрат соответствующего коэффициента ak минус удвоенное произведение соседних коэффициентов с ak плюс удвоенное произведение следующей пары соседей , чередуя знаки, пока в число соседних коэффициентов не попадут а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

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

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

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

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

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

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

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

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

МЕТОД ОБРАТНОЙ МАТРИЦЫ

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

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

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

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

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

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

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

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

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

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