Реферат: Численные методы алгебры

называется корнемуравнения (1) или нулем функции f(x).

Задача нахождения корня уравнения f(x) = 0 итерационным методом состоит из двух этапов:

1. отделение корней - отыскание приближенного значения корня или содержащего его отрезка;

2. уточнение приближенных корней - доведение их до заданной степени точности.

Процесс отделения корней начинается с установления знаков функции f(x) в граничных x = a и x = b точках области ее существования.

Пример 1. Отделить корни уравнения:

Составим приблизительную схему:

Следовательно, уравнение (2) имеет три действительных корня, лежащих в интервалах [-3, -1], [0, 1] и [1, 3].

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

В инженерной практике распространен графический способ определения приближенных корней.

Принимая во внимание, что действительные корни уравнения (1) - это точки пересечения графика функции f(x) с осью абсцисс, достаточно построить график функции f(x) и отметить точки пересечения f(x)с осью Ох, или отметить на оси Ох отрезки, содержащие по одному корню. Построение графиков часто удается сильно упростить, заменив уравнение (1) равносильным ему уравнением:

где функции f₁(x) и f₂(x) - более простые, чем функция f(x). Тогда, построив графики функций у = f₁(x) и у = f₂(x), искомые корни получим как абсциссы точек пересечения этих графиков.

Рисунок 2.

Пример 2.Графически отделить корни уравнения (Рисунок 2):

Уравнение (4) удобно переписать в виде равенства:

lg x=.

Отсюда ясно, что корни уравнения (4) могут быть найдены как абсциссы точек пересечения логарифмической кривой y = lg x и гиперболы y = . Построив эти кривые, приближенно найдем единственный корень уравнения (4) или определим его содержащий отрезок [2, 3].

Итерационный процесс состоит в последовательном уточнении начального приближения х₀. Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня х₁, х₂, ..., х_n. Если эти значения с увеличением числа итераций n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится.

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

Для использования метода итерации исходное нелинейное уравнение f(х) = 0 заменяется равносильным уравнением

Пусть известно начальное приближение корня х = х₀. Подставляя это значение в правую часть уравнения (8), получим новое приближение:

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

Геометрически метод итерации может быть пояснен следующим образом. Построим на плоскости хОу графики функций у = х и у = j(х). Каждый действительный корень уравнения (8) является абсциссой точки пересечения М кривой у = ?(х) с прямой у = х (Рисунок 6, а).

Рисунок 6.

Отправляясь от некоторой точки А₀[x₀,j(x₀)], строим ломаную А₀В₁А₁В₂А₂... (“лестница”), звенья которой попеременно параллельны оси Ох и оси Оу, вершины А₀, А₁, А₂, ...лежат на кривой у=j(х), а вершины В₁, В₂, В₃, …, - на прямой у = х. Общие абсциссы точек А₁ и В₁, А₂ и В₂, ..., очевидно, представляют собой соответственно последовательные приближения х₁, х₂, ... корня .

Возможен также другой вид ломаной А₀В₁А₁В₂А₂ ... - “спираль” (Рисунок 6, б). Решение в виде “лестницы” получается, если производная j' (х) положительна, а решение в виде “спирали”, если j' (х) отрицательна.

На Рисунке 6, а, б кривая у = j (х) в окрестности корня - пологая, то есть <1, и процесс итерации сходится. Однако, если рассмотреть случай, где >1, то процесс итерации может быть расходящимся (Рисунок 7).

Рисунок 7.

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

Теорема: Пусть функция? (х) определена и дифференцируема на отрезке [a, b], причем все ее значения? (х) [a, b].

Тогда, если существует правильная дробьqтакая, что

q < 1

при a < x < b,то: 1) процесс итерации

сходится независимо от начального значения х_{0 ?}[a, b];

2) предельное значениеявляется единственным корнем уравнениях = j(х) на отрезке [a, b].

Пример 5. Уравнение

имеет корень x--[1, 2], так как f(1) = - 1 < 0 и f(2) = 5 > 0.

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

Здесь

j (х) = х³ - 1 и j' (х) = 3х²;

поэтому

j' (х) 3 при 1 х2

и, следовательно, условия сходимости процесса итерации не выполнены.

Если записать уравнение (10) в виде

то будем иметь:

.

Отсюда при 1 х2 и значит, процесс итерации для уравнения (12) быстро сойдется.

Найдем корень ? уравнения (10) с точностью до 10^-2. Вычисляем последовательные приближения х_nс одним запасным знаком по формуле

Найденные значения помещены в Таблицу 1:

Таблица 1. Значения последовательных приближений x_i.

С точностью до 10^-2 можно положить ? = 1,324.

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

3.1 Приведение системы к виду, удобному для итераций

Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений

Ax = b

с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

x = Bx + c.

Здесь B - квадратная матрица с элементами b_ij (i, j = 1, 2, …, n), c - вектор-столбец с элементами c_ij(i = 1, 2, …, n).

В развернутой форме записи система имеет следующий вид:

x₁ = b₁₁x₁ + b₁₂x₂ + b₁₃x₃ + … + b_1nx_n + c₁

x₂ = b₂₁x₁ + b₂₂x₂ + b₂₃x₃ + … + b_2nx_n + c₂

. . . . . . . . . . . . . . . . .

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_nnx_n + c_n

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x₁:

x₁ = a₁₁-¹ (b₁ - a₁₂x₂ - a₁₃x₃ - … - a_1nx_n),

из второго уравнения - неизвестное x₂:

x₂ = a₂₁-¹ (b₂ - a₂₂x₂ - a₂₃x₃ - … - a_2nx_n),

и т. д. В результате получим систему

x₁ = b₁₂x₂ + b₁₃x₃ + … + b_1,n-₁x_n-₁ + b_1nx_n+ c₁ ,

x₂ = b₂₁x₁ + b₂₃x₃ + … + b_2,n-₁x_n-₁ + b_2nx_n+ c₂ ,

x₃ = b₃₁x₁ + b₃₂x₂ + … + b_3,n-₁x_n-₁ + b_3nx_n+ c₃ ,

. . . . . . . . . . . . . . . . . . . . . . .

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_n,n-₁x_n-₁ + c_n ,

в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам

b_ij = -a_ij / a_ii, c_i = b_i / a_ii (i, j = 1, 2, …, n, j ? i)

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

3.2. Описание метода

Введем нижнюю и верхнюю треугольные матрицы

0 0 0 … 0 0 b₁₂ b₁₃ … b_1n

b₂₁ 0 0 … 0 0 0 b₂₃ … b_2n

B₁ = b₃₁ b₃₂ 0 … 0 , B₂ = 0 0 0 … b_3n

. . . . . . . . . . . . . .

b_n1 b_n2 b_n3 … 0 0 0 0 … 0

Заметим, что B = B₁+ B₂ и поэтому решение x исходной системы удовлетворяет равенству

x = B₁x + B₂ x + c .

Выберем начальное приближение x⁽⁰⁾ = [x₁⁽⁰⁾, x₂⁽⁰⁾, …, x_n⁽⁰⁾]^T. Подставляя его в правую часть равенства при верхней треугольной матрице B₂и вычисляя полученное выражение, находим первое приближение

x⁽¹⁾ = B₁x⁽⁰⁾ + B₂x⁽¹⁾

Подставляя приближение x⁽¹⁾, получим

x⁽²⁾ = B₁x⁽¹⁾ + B₂x⁽²⁾

Продолжая этот процесс далее, получим последовательность x⁽⁰⁾, x⁽¹⁾, …, x⁽ⁿ⁾, … приближений к вычисляемых по формуле

x^(k+1) = B₁^(k+1) + B₂^(k) + c

или в развернутой форме записи

x₁^(k+1) = b₁₂x₂^(k) + b₁₃x₂^(k) + … + b_1nx_n^(k) + c₁ ,

x₂^(k+1) = b₂₁x₁^(k+1) + b₂₃x₃^(k) + … + b_2nx_n^(k) + c₂ ,