Метод хорд (секущих, ложного положения)

⇐ ПредыдущаяСтр 6 из 6

Пусть задано уравнение (6.1), где f(x) – непрерывна и найден интервал [a, b], содержащий один корень, т.е. f(а)∙ f(b) < 0.

В основе метода лежит линейная интерполяция по 2 значениям функции, имеющим разные знаки.

Уравнение хорды АВ

(6.5)

В качестве приближений к корню принимаются значения с₀, с₁,..., с – точек пересечения хорд с осью абсцисс.

Для точки пересечения с осью х хорды АВ (х = с₀, y = 0) получим уравнение

Если f(c₀)∙ f(b) < 0, корень на интервале [c₀, b],

Следующая итерация: точка c₁ пересечения с осью х хорды BD (х = с₁, y = 0), а = с₀ и т.д.

(6.6)

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

Оценка погрешности n – го приближения

(6.7)

где , . (6.8)

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

Пусть задано уравнение (6.1), где f(x) – непрерывна и найден интервал [a, b], содержащий только один корень, с₀ – начальное приближение.

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

Вместо интерполяции осуществляется экстраполяция с помощью касательной к кривой в данной точке (ее пересечение с осью абсцисс).

В основе лежит разложение в ряд Тейлора

или

Дано f(x) = 0, x Î [a, b],

c₀ – начальное приближение

Уравнение касательной в т. М₀(c₀, f(c₀))

Первое приближение c₁– абсцисса точка пересечения касательной к точке М₀ с осью х (c₁, 0).

Из выражения

получим и т.д.

, n = 0, 1, 2, … (6.9)

Замечание: начальное приближение c₀ целесообразно выбирать так, чтобы

(6.10)

Теорема (достаточное условие сходимости):

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

Трудности метода Ньютона состоят в определении:

1) начального приближения x = c₀, которое должно находиться вблизи корня уравнения;

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

Объем вычислений метода Ньютона больше, но скорость сходимости выше.

Этот метод не рекомендуется при почти горизонтальных графиках кривых.

Оценка погрешности n – го приближения

(6.11)

где .

При этом быстрая сходимость обеспечена, если начальное приближение c₀ удовлетворяет неравенству

(6.12)

Метод простой итерации

Пусть задано уравнение (6.1), где f(x) – непрерывна и найден интервал [a, b], содержащий только один корень.

Уравнение (6.1) представим в виде

x = j (x) (6.13)

Выбираем начальное приближение x = c₀ и, подставив в (6.13), находим следующее приближение c₁ = j (c₀) и т.д.

По аналогии

с_n₊₁ = j (c_n), n = 0, 1, 2, … (6.14)

Геометрическая интерпретация метода:

Строим графики функций y = x и y = j (x) (левая и правая части уравнения (6.13)).

Каждый действительный корень с является абсциссой точки пересечения кривой y = j (x) и прямой y = x.

Оценка погрешности n – го приближения

, (6.15)

где .

Тема 7

Решение систем нелинейных уравнений (сну)

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

(7.1)

………

В отличие от систем линейных уравнений для систем нелинейных уравнений не существует прямых методов решения, поэтому всегда применяются итерационные методы.

Метод простой итерации

Метод простой итерации для СНУ является развитием аналогичного метода для решения одного уравнения. Он основан на допущении, что систему (7.1) можно привести к виду

(7.2)

………

Эта разновидность метода простой итерации построена аналогично методу Зейделя для СЛУ, когда для нахождения каждого последующего значения неизвестных используются вновь найденные значения предыдущих приближений.

(7.3)

………

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

, i = 1, 2, …, n (7.4)

Недостаток метода:

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

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

Метод Ньютона

Совокупность аргументов x₁, x₂, …, x_n системы (7.1) можно рассматривать как n - мерный вектор, а совокупность функций f₁, f₂, …, f_n как n - мерный вектор – функцию.

, .

Уравнение (7.1) можно записать в матричном виде

(7.5)

Приближенно заменим систему (7.5) линейной алгебраической системой.

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

(7.6)

Определителем полученной системы линейных уравнений (7.6) относительно является определитель матрицы Якоби (якобиан), подсчитанный для

(7.7)

Для существования единственного решения системы (7.1) якобиан системы (7.7) должен быть отличен от 0 на каждой итерации.

Если , то (7.6) можно переписать

и т.д. (7.8)

Таким образом,

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

, i = 1, 2, …, n ...

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

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

. (7.10)

Принятое допущение используется при построении расчетной формулы модифицированного метода Ньютона

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

Литература

1. Березин И.С., Жидков Н.П. Методы вычислений. –М.: Физматгиз, 1962

2. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. -М., 1963

3. Калиткин Н.Н. Численные методы. –М.,: Наука, 1978.

4. Самарский А.А., Гулин А.В. Численные методы. –М.,: Наука, 1989

⇐ Предыдущая 1 2 3 4 56