Метод простой итерации ( метод Якоби)

Метод деления пополам

Пусть на отрезке локализован корень уравнения .

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

если или если .

Пусть на к-м шаге найден отрезок . Тогда на к+1 шаге

.

Алгоритм завершается, если для некоторого к окажется , где требуемая точность решения. Тогда значение корня Если задана абсолютная точность определения корня , то алгоритм завершается при условии . В этом случае за приближенное значение корня принимается

Метод хорд

Пусть — абсциссы концов хорды, Найдем коэффициенты и из системы уравнений:

.

Вычтем из первого уравнения второе:

, затем найдем коэффициенты и :

, тогда

.

Уравнение принимает вид:

Таким образом, теперь можем найти первое приближение к корню, полученное методом секущих:

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

.

Повторять операцию следует до тех пор, пока не станет меньше или равно заданному значению погрешности.

Метод касательных

Пусть на отрезке существует единственный корень уравнения (1): ,

а существует, непрерывна и отлична от нуля на . Перепишем (2) следующим образом:

и применим к этому выражению формулу Лагранжа:

Выразим отсюда :

Метод касательных имеет (когда сходится) квадратичную скорость сходимости

Модифицированный метод касательных

Если мы хотим избежать вычисления производной на каждом шаге, то можно взять вместо где - начальное приближение:

В отличие от обычного метода касательных, в модифицированном методе предоставляется меньше требований к выбору начального приближения, а так же гарантировано отсутствие деления на ноль, если

Метод простых итерации.

Для построения рабочей формулы уравнение преобразуется к виду:

. (1)

Далее итерационный процесс строится по формуле

(2)

Для сходимости итерационного процесса (2) необходимо задать произвольное начальное приближение из отрезка , для которого выполняется условие:

(3)

Процесс (3) заканчивается при одновременном выполнении двух условий: и . В этом случае значение является приближенным значением корня нелинейного уравнения на отрезке .

К виду x=j(x), удобному для итераций, уравнение f(x)=0 можно привести разными способами. Один из способов заключается в следующем. Уравнение записывается в виде

x=x+сf(x)

Здесь функция . Тогда Константа выбирается из условия сходимости (3). Если производная , то значение выбирается из интервала , если производная , то – из интервала .

Комбинированный метод

Суть комбинированного метода состоит в разбиении отрезка [a,b] (при условии f(a)f(b)<0) на три отрезка с помощью хорды и касательной и выборе нового отрезка от точки пересечения хорды с осью абсцисс до точки пересечения касательной с осью абсцисс, на котором функция меняет знак и содержит решение.

Условие начальной точки для метода хорд f(x)f”(x)<0.
Условие начальной точки для метода касательных f(x)f”(x)>0.

Входные данные: f(x), f’(x), f”(x), a, b, ε.

Значение x является решением с заданной точностью ε нелинейного уравнения вида f(x)=0.
Если f(x)=0, то x - точное решение.

Метод Гаусса

Дана система уравнений (1). Будем считать, что матрица системы А – неособенная. Требуется найти решение системы – вектор Х*.
Схема единственного деления

Для удобства вычислений используют расширенную матрицу ( ), (n+1)-й столбец которой – столбец свободных членов системы - b:

.

Прямой ход.На каждом из шагов с номерами k = 1, …, n-1 выбираем ведущую строку с номером k и ведущий элемент . Далее выполняем следующие операции.

1). Все элементы ведущей строки расширенной матрицы делим на :

. (2)

2). Из всех строк расширенной матрицы с номерами i > k вычитаем ведущую строку, умноженную на элемент , получая нули под ведущим элементом:

. (3)

3). Увеличиваем номер ведущей строки: k = k +1 и, если k < n, повторяем 1), 2). Если k = n, то прямой ход закончен.

Обратный ход. По формулам

(4)

находим решение системы ^T .

Метод Жордана-Гаусса

Этот метод, как и метод Гаусса, является методом исключения, предназначенным для системы линейных уравнений ( матрица А – невырожденная). Отличие от схем метода Гаусса в том, что путем преобразований матрица А приводится не к треугольному, а к диагональному виду. В результате исходная система линейных уравнений приобретает вид:

Обратный ход в схемах Жордана становится формальностью.
Как и в схемах Гаусса, здесь удобно использовать расширенную матрицу системы . Классическая схема Жордана реализуется за n шагов. Описание k-го шага (k =1,2...n).
1). Делим k- ю строку расширенной матрицы на элемент :

j = 1, 2, ...,n + 1.

2). Из строк с номерами вычитаем k-ю строку, умноженную на числовой коэффициент так, чтобы в k-ом столбце расширенной матрицы получить нули над и под элементом :

ж j = 1, 2, ...,n + 1.

Если элементы главной диагонали матрицы в процессе работы метода оказываются равными или близкими к нулю, то можно использовать модификации метода с перестановкой строк или столбцов, аналогичные соответствующим модификациям метода Гаусса

Метод Якоби

Метод простой итерации ( метод Якоби)

Пусть система линейных алгебраических уравнений (СЛАУ) задана в виде

Предположим, что диагональные элементы исходной системы не равны нулю (a_ii ≠ 0, i = 1, 2, …, n). Разрешим первое уравнение системы относительно x₁, второе относительно x₂ и т.д. Получим следующую эквивалентную систему:

(6)

В системе (6) -ое уравнение представляет собой -ое уравнение системы (6), разрешённое относительно –ой неизвестной ( ).

Теперь, задав нулевое приближение , по соотношениям (5) можем выполнять итерационный процесс. Таким образом, рабочие формулы метода простой итерации решения системы (5) будут иметь вид

Формулы (2.3) можно записать в виде

Условие окончания итерационного процесса

, .

Достаточное условие сходимости. Если выполнено условие диагонального преобладания, то есть

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

См.15

Метод Зейделя

Дана система линейных уравнений

,(1)

где -квадратная невырожденная матрица.

Представив A в виде суммы двух матриц , где ; , запишем (1) в виде:

(1a)

Уравнение (1a) преобразуем в реккурентную формулу метода Зейделя:

, k = 0,1,2,… (2)

Вычитая из обеих частей (2) , получим представление (2) в виде:

, k = 0,1,2,… (2a)

Обозначив , , получим расчетные формулы метода Зейделя в матричном виде:

; , 0, 1, ... (3).

Из (2) можно получить расчетные формулы для в координатной форме:

, 1, ..., n, 0, 1, ... . (4)

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

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

(5).

Не нашли, что искали? Воспользуйтесь поиском по сайту: