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

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

Модификацией метода простых итераций Якоби можно считать метод Зейделя.

В методе Якоби на (k+1)-ой итерации значения x, i = 1, 2, …, n. вычисляются подстановкой в правую часть (3.27) вычисленных на предыдущей итерации значений x. В методе Зейделя при вычислении xиспользуются значения x, x, x, уже найденные на (k+1)-ой итерации, а не x, x, …, x, как в методе Якоби, т.е. (k + 1)-е приближение строится следующим образом:

 x =  b₁₂ x + b₁₃ x + … + b_1,n-1 x + b_1n x + c₁

x = b₂₁ x+ b₂₃ x + … + b_2,n-1 x + b_2n x + c₂

x= b₃₁ x + b₃₂ x + … + b_3,n-1 x  +b_3n x   + c₃ (3.36)

x= b_n1 x + b_n2 x x + b_n3 x x+ … + b_n,n-1 x+ c._n

Формулы (3.36) являются расчетными формулами метода Зейделя.

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

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

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

B₁ = b₃₁ b₃₂ 0 … 0 и  B₂ =0 0 0 … b_{3n .}

b_n1 b_n2 b_n3 …00 0 0 … 0

Матричная запись расчетных формул (3.36) имеет вид:

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

Так как B = B₁+ B₂, точное решение x^* исходной системы удовлетворяет равенству:

x^*= B₁x^*+ B₂x^*+ c.  (3.38)

Сходимость метода Зейделя. Достаточным условием сходимости метода Зейделя является выполнение неравенства:

b = max |b_ij|,< 1, i, j = 1, 2, …, n.  (3.39)

Неравенство (3.39) означает, что для сходимости метода Зейделя достаточно, чтобы максимальный по модулю элемент матрицы B был меньше единицы.

Если выполнено условие (3.39), то справедлива следующая апостериорная оценка погрешности:

max|x - x| £ max|x– x| i = 1, 2, …, n, (3.40)

где b – максимальный элемент матрицы B, b₂ – максимальный элемент матрицы B₂.

Правую часть оценки (3.40) легко вычислить после нахождения очередного приближения.

Критерий окончания. Если требуется найти решение с точностью e, то в силу (3.37) итерационный процесс следует закончить как только на (k+1)-ом шаге выполнится неравенство:

max|x– x| < e, i = 1, 2, …, n. (3.41)

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

max|x– x| < e₁, i = 1, 2, …, n. (3.42)

где e_{1 =} e_.

Если выполняется условие b £ , то можно пользоваться более простым критерием окончания:

max|x– x| < e, i = 1, 2, …, n. (3.43)

Метод Зейделя как правило сходится быстрее, чем метод Якоби. Однако возможны ситуации, когда метод Якоби сходится, а метод Зейделя сходится медленнее или вообще расходится.

Пример 3.6.

Применим метод Зейделя для решения системы уравнений (3.33) из примера 3.5. Первые шаги полностью совпадают с процедурой решения по методу Якоби, а именно: система приводится к виду (3.34), затем в качестве начального приближения выбираются элементы столбца свободных членов (3.35). Проведем теперь итерации методом Зейделя.

При k = 1

x   = – 0.0574x  – 0.1005x – 0.0431x + 1.0383 = 0.7512

При вычислении xиспользуем уже полученное значение x:

x  = –0.0566 x   – 0.0708x – 0.1179x + 1.2953 = 0.9674

При вычислении x используем уже полученные значения x и x:

x  = –0.1061 x – 0.0758 x – 0.0657x + 1.4525 = 1.1977

При вычислении x используем уже полученные значения x, x, x:

x = –0.0280 x – 0.0779 x – 0.0405x x + 1.5489 = 1.4037

Аналогичным образом проведем вычисления при k = 2 и k = 3. Получим:

при k = 2

x= 0.8019, x= 0.9996,  x= 1.9996, x= 1.4000.

при k = 3

x= 0.80006, x= 1.00002, x= 1.19999, x= 1.40000.

Известны точные значения переменных:

x₁ = 0.8, x₂ = 1.0, x₃ = 1.2, x₄ = 1.4.

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

Тема 4. Приближение функций

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

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

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

2. Функция задана аналитически, но ее вычисление по формуле затруднительно.

При решении задачи поиска приближенной функции возникают следующие проблемы.

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

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

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

4.2 Приближение функции многочленами Тейлора

Пусть функция y = f(x) определена в окрестности точки a и имеет в этой окрестности n + 1 производную. Тогда в этой окрестности справедлива формула Тейлора:

f(x) = c₀ + c₁(x – a) + c₂(x – a)² + … + c_n(x – a )ⁿ + R_n(x) = T_n(x) + R_n(x),

где

c_k =

T_n(x) – многочлен Тейлора:

T_n(x)= c₀ + c₁(x – a) + c₂(x – a)² + … + c_n(x – a )ⁿ, (4.1)

R_n(x) – остаточный член формулы Тейлора. Его можно записать различными способами, например, в форме Лагранжа:

R_n(x)= , a £ x £ x.

Многочлен Тейлора (4.1) обладает свойством, что в точке x = a все его производные до порядка n включительно совпадают с соответствующими производными функции f, т. е.

T(a)= f^(k)(a), k = 0, 1, …, n.

В этом легко убедиться, дифференцируя T_n(x). Благодаря этому свойству многочлен Тейлора хорошо приближает функцию f в окрестности точки a. Погрешность приближения составляет

|f(x) – T_n(x)| = |R_n(x)|,

т. е. задавая некоторую точность e > 0, можно определить окрестность точки a и значение n из условия:

|R_n(x)| =  < e.  (4.2)

Пример 4.1.

Найдем приближение функции y = sinx многочленом Тейлора в окрестности точки a = 0. Воспользуемся известным выражением для k-ой производной функции sinx:

(sinx)^(k) = sin x + k (4.3)

Применяя последовательно формулу (4.3), получим:

f(0) = sin0 = 0;

f '(0) = cos(0) = 1;

f"(0) = –sin0 = 0;

f^(2k-1)(0) = sin (2k – 1) = (–1)^{k – 1} ;

f^(2k)(0) = 0;

f^(2k+1)(x) = (–1)^kcosx.

Следовательно, многочлен Тейлора для функции y = sinx для n = 2k имеет вид:

sinx = x – + … + (–1)^{k – 1} + R_2k(x),

R_2k(x) = (–1)^k .

Зададим e = 10 ^–4 и отрезок [–,]. Определим n =2k из неравенства:

|R_2k(x)| =  < < < e = 10^-4.

Таким образом, на отрезке –, функция y = sinx с точностью до e = 10^-4 равна многочлену 5-ой степени:

sinx = x – +  = x – 0.1667x³ + 0.0083x⁵.

Пример 4.2.

Найдем приближение функции y = e^x многочленом Тейлора на отрезке [0, 1] с точностью e = 10 ^–5.

Выберем a = ½, т. е в середине отрезка. При этом величина погрешности в левой части (4.2) принимает минимальное значение. Из математического анализа известно, что для k-ой производной от e^x справедливо равенство:

(e^x)^(k) = e^x.

Поэтому

(e^a)^(k)  = e^a = e^1/2,

Следовательно, многочлен Тейлора для функции y = e^x имеет вид:

e^x = e^{1/2 +} e^1/2(x – ½) + (x – ½)² + … +  (x – ½)ⁿ+ R_n(x),

При этом, учитывая, что xÎ [0, 1], получим оценку погрешности:

|R_n(x)| < . (4.4)

Составим таблицу погрешностей, вычисленных по формуле (4.4):

Таким образом, следует взять n = 6.

Похожие работы

Лекции по вычислительной математике

Скачать

10356

0

0

... . Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного примера. Пользуясь введенными здесь обозначениями, мы проводим это описание в следующей лекции. Введем некоторые термины. Пусть имеется некоторая чис- ловая матрица. Привести строку этой матрицы означает выде-лить в строке минимальный элемент (его называют константой приведения) ...

Основные задачи вычислительной математики

Скачать

7721

1

1

... если  - предельная абсолютная погрешность приближённого числа , то  (1.2) отсюда следует, что  (1.3) Значение предельной абсолютной погрешности, обычно, подбирается интуитивно по смыслу задачи. Пример 2: Определить предельную абсолютную погрешность числа , заменяющего число , точное значение которого нам неизвестно. Так как мы знаем, что , ...

Выдающиеся личности в истории вычислительной техники. Августа Ада Лавлейс

Скачать

37333

0

0

... удивили меня…, хоть речь идёт обо мне самой. Они действительно написаны прекрасным стилем, который превосходит стиль самого очерка" /2/. 2.3. Рождение первенца и критическое перенапряжение Августа Ада Лавлейс работает с большим напряжением. В письмах к Бэббиджу она неоднократно жалуется на утомление, болезни, плохое самочувствие. Наконец, 6 августа Бэббидж отсылает Аде свои последние замечания ...

Роль женщин в развитии вычислительной техники

Скачать

54819

0

0

... в Украине, бывшем Советском Союзе и за рубежом научная школа теоретического программирования. В 2001-м году ее не стало... Но не только в научном плане велика роль женщин в развитии вычислительной техники. Со временем образуется огромное количество различных фирм по разработке и продаже программного и аппаратного обеспечения. Следовательно, разыгрываются человеческие трагедии капиталистического ...