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

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

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

где α — угол наклона касательной в точке  .

Следовательно искомое выражение для   имеет вид:

Билет№28

Численные методы.  Разрешимость системы линейных уравнений.  Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу nЧn, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.  Если, например, количество строк (количество уравнений в системе) будет меньше, чем количество столбцов (фактически, количества неизвестных), то система будет неопределенной, т. е. мы не сможем однозначно определить все неизвестные (решить систему).  Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.  Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:  1.           Δ = 0 и каждый из дополнительных определителей Δx_i = 0. Это имеет место только тогда, когда коэффициенты при неизвестных x_i пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число k. При этом система имеет бесчисленное множество решений.  2.           Δ = 0 и хотя бы один дополнительный определитель Δx_i ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных x_i, пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений. 

Постановка задачи

Пусть есть функция  . Требуется найти корень этой функции: такой   при котором  Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций.

Метод простых итераций в общем виде

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

Билет№29

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

Метод Зейделя (иногда называемый методом Гаусса-Зейделя) является модификацией метода простой итерации, заключающейся в том, что при вычислении очередного приближения x^(k+1) (см. формулы (1.13),(1.14)) его уже полученные компоненты x₁^(k+1), ...,x_{i - 1}^(k+1) сразу же используются для вычисления x_i^(k+1).

В координатной форме записи метод Зейделя имеет вид:

x₁^(k+1) = c₁₁x₁^(k) + c₁₂x₂^(k) + ... + c_1n-1x_n-1^(k) + c_1nx_n^(k) + d₁ x₂^(k+1) = c₂₁x₁^(k+1) + c₂₂x₂^(k) + ... + c_2n-1x_n-1^(k) + c_2nx_n^(k) + d₂ ... x_n^(k+1) = c_n1x₁^(k+1) + c_n2x₂^(k+1) + ... + c_nn-1x_n-1^(k+1) + c_nnx_n^(k) + d_n где x⁽⁰⁾ - некоторое начальное приближение к решению.

Таким образом i-тая компонента (k+1)-го приближения вычисляется по формуле

xi^(k+1) = ∑ j=1^i-1 cijxj^(k+1) + ∑ ^nj=i cijxj^(k) + di , i = 1, ..., n

(1.20)

Условие окончания итерационного процесса Зейделя при достижении точности ε в упрощенной форме имеет вид:

|| x ^(k+1) - x ^(k) || ≤ ε.

Билет№30