Метод зейделя в excel
Метод Зейделя представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (k+1)-го приближения неизвестной xi учитываются уже вычисленные ранее (k+1) – е приближения неизвестных x1, х2, .
В этом методе, как и в методе простой итерации, необходимо привести систему к виду (3), чтобы диагональные коэффициенты были максимальными по модулю, и проверить условия сходимости. Если условия сходимости не выполняются, то нужно произвести элементарные преобразования (см. п. 4). Пусть дана система из трех линейных уравнений. Приведем ее к виду (3). Выберем произвольно начальные приближения корней: х1(0), х2(0), х3(0), стараясь, чтобы они в какой-то мере соответствовали искомым неизвестным. За нулевое приближение можно принять столбец свободных членов, т. е. х(0) = b
(т. е. x1(0)=b1, x2(0)=b2, x3(0)=b3). Найдем Первое приближение х(1) по формулам:
Следует обратить внимание на особенность метода Зейделя, которая состоит в том, что полученное в первом уравнении значение х1(l) сразу же используется во втором уравнении, а значения х1(1), х2(1) – в третьем уравнении и т. д. То есть все найденные значения х1(1) подставляются в уравнения для нахождения хi+1(1) [6, 8].
Рабочие формулы для метода Зейделя для системы трех уравнений имеют следующий вид:
Запишем в общем виде для системы n-уравнений рабочие формулы:
Заметим, что теорема сходимости для метода простой итерации справедлива и для метода Зейделя.
Зададим определенную точность решения e, по достижении которой итерационный процесс завершается, т. е. решение продолжается до тех пор, пока не будет выполнено условие для всех уравнений: где i=1,2,3,…,n.
Пример №2. Методом Зейделя решить систему с точностью e = 10-3:
1. Приведем систему к виду:
2. В качестве начального вектора х(0) возьмем элементы столбца свободных членов, округлив их значения до двух знаков после запятой:
3. Проведем итерации методом Зейделя. При k = 1
При вычислении х2(1) используем уже полученное значение х1(1) =
При вычислении х3(1) используем значения х1(1) и х2(1):
Наконец, используя значения х1(1), х2(1), х3(1), получаем:
Аналогичным образом ведем вычисления при k=2 и k=3. При k= 2:
Найдем модули разностей значений при k = 2:
Они меньше заданного числа e, поэтому в качестве решения возьмем: x1 = 0,80006, x2 = 1,00002, x3 = 1,19999, x4 = 1,40000.
Назначение сервиса . Сервис предназначен для решения СЛАУ в онлайн режиме методом Зейделя. Дополнительно генерируется шаблон решения в Excel . Метод Зейделя представляет собой модификацию метода простой итераций.
Метод Зейделя представляет собой модификацию метода простой итераций.
Пусть дана приведённая система:
и известно начальное приближение (x 0 1, x 0 2. x 0 n)=x 0 . Основная идея заключается в том, что при вычислении (k+1) - го приближения неизвестной xi учитываются уже вычисленные ранее (k+1) - приближение неизвестных x1, x2, . xi-1.
Итерационная схема имеет вид:
Положим α = B + C, где
; .
Тогда процесс Зейделя в матричном виде можно записать как:
x k +1 = B x k +1 + C x k + β
Процесс Зейделя для нормальной системы
- матрица С – симметрическая;
- все элементы главной диагонали cij > 0;
- матрица С - положительно определена.
Достаточные условия сходимости итерационной последовательности
Достаточные условия сходимости итерационной последовательности приближенных решений системы и оценка погрешности проводятся по тем же формулам, что и в методе простой итерации.
Пример №1 . Рассмотрим вычисление двух приближений по методу Зейделя для примера, решенного выше для метода простой итерации и оценим погрешность.
Вычисления будем проводить по формулам:
Выбираем начальное приближение: x (0) =(0;0;0) и получаем:
x (1) =(-1,9022;0,6791;1,2091), x (2) =(-1,6004;0,6291;1,3498).
Пример №2 . Система двух Линейных Алгебраических Уравнения (СЛАУ) с двумя неизвестными задана своей расширенной матрицей. Решите СЛАУ методом Зейделя с точностью до 0.001. Поменяйте порядок уравнений в СЛАУ и решите полученную таким образом СЛАУ тем же методом Зейделя. Постройте графики уравнений СЛАУ в обоих СЛАУ в обоих случаях и покажите на них первые три-четыре итерации.
Пример №3 . Методом Зейделя решить с точностью 0,001 систему линейных уравнений, приведя ее к виду, удобному для итерации.
3.6x1 + 1.8x2 - 4.7x3 = 3.8
2.7x1 - 3.6x2 + 1.9x3 = 0.4
1.5x1 + 4.5x2 + 3.3x3 = -1.6
Решение. Умножаем матрицы A T A.
Приведем к виду:
x1=0.55+0.16x2-0.3x3
x2=-0.0494+0.0963x1-0.0123x3
x3=-0.61-0.19x1-0.0123x2
Покажем вычисления на примере нескольких итераций.
N=1
x1=0.55 - 0 • 0.16 - 0 • (-0.3)=0.55
x2=-0.0494 - 0.55 • 0.0963 - 0 • (-0.0123)=-0.1
x3=-0.61 - 0.55 • (-0.19) - (-0.1) • (-0.0123)=-0.51
N=2
x1=0.55 - (-0.1) • 0.16 - (-0.51) • (-0.3)=0.41
x2=-0.0494 - 0.41 • 0.0963 - (-0.51) • (-0.0123)=-0.0952
x3=-0.61 - 0.41 • (-0.19) - (-0.0952) • (-0.0123)=-0.54
N=3
x1=0.55 - (-0.0952) • 0.16 - (-0.54) • (-0.3)=0.4
x2=-0.0494 - 0.4 • 0.0963 - (-0.54) • (-0.0123)=-0.0946
x3=-0.61 - 0.4 • (-0.19) - (-0.0946) • (-0.0123)=-0.54
Остальные расчеты сведем в таблицу.
N | x1 | x2 | x3 | e1 | e2 | e3 |
0 | 0 | 0 | 0 | |||
1 | 0.55 | -0.1 | -0.51 | 0.55 | 0.1 | 0.51 |
2 | 0.41 | -0.0952 | -0.54 | -0.14 | -0.0071 | 0.0259 |
3 | 0.4 | -0.0946 | -0.54 | -0.00899 | -0.000546 | 0.00167 |
4 | 0.4 | -0.0946 | -0.54 | -0.000594 | -3.7E-5 | 0.000111 |
Пример №4 . Выполнить три итерации по методу Зейделя для системы уравнений Ax=b (не переставляя строк). В качестве начального приближения взять нулевой вектор. Изобразить графически поведение итерационного процесса. Сопоставить его сходимость с выполнением достаточных условий сходимости метода.
Метод простой итерации даёт возможность получить последовательность приближённых значений, сходящуюся к точному решению системы.
Преобразуем систему (3.1) к нормальному виду:
. (3.2)
Правая часть системы (3.2) определяет отображение:
x=(x1, x2, . xn), преобразующее точку n -мерного метрического пространства в точку y=(y1, y2, . yn) того же пространства.
Выбрав начальную точку x 0 =(x 0 1, x 0 2, . x 0 n), можно построить итерационную последовательность точек n - мерного пространства: x 0 , x 1 =F(x 0 ), . , x n+1 =F(x n )
При определённых условиях данная последовательность сходится.
Так, для исследования сходимости таких последовательностей используется принцип сжимающих отображений, который состоит в следующем.
Если F– сжимающее отображение, определённое в полном метрическом пространстве с метрикой ρ(x,y), то существует единственная неподвижная точка x*, такая, что x*=F(x*). При этом итерационная последовательность, n>, полученная с помощью отображения F с любым начальным членом х (0) , сходится к x*.
Оценка расстояния между неподвижной точкой x* отображения F и приближением х (к) даётся формулами:
(3.3)
где α – множитель, определяемый достаточными условиями сжимаемости отображения F.
Значение множителя α, определяется выбором метрики, в которой проверяется сходимость последовательности значений xi.
Рассмотрим достаточные условия сходимости итерационной последовательности n>.
Практически, для применения метода итерации систему линейных уравнений удобно "погрузить" в одну из трёх следующих метрик:
(3.4)
Для того, чтобы отображение F, заданное в метрическом пространстве соотношениями (3.2), было сжимающим, достаточно выполнение одного из следующих условий:
а) в пространстве с метрикой ρ1: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по строкам, должна быть меньше единицы.
б) в пространстве с метрикой ρ2: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по столбцам, должна быть меньше единицы.
в) в пространстве с метрикой ρ3: , т. е. сумма квадратов при неизвестных в правой части системы (3.2) должна быть меньше единицы
Пример . Вычислить два приближения методом простой итерации. Оценить погрешность второго приближения. В качестве начального приближения выбрать x 0 =(0; 0; 0).
Так как диагональные элементы системы являются преобладающими, то приведем систему к нормальному виду:
Последовательные приближения будем искать по формулам:
Получаем:
x 1 =(-1.9022; 0.4889; 2.1456), x 2 =(-1.1720; 0.6315; 1.2389).
Для оценки погрешности в метрике ρ1 вычисляем коэффициент μ
.
Вычисляем погрешность:
При большом числе неизвестных схема метода Гаусса, дающая точное решение, становится весьма сложной. В этом случае для решения СЛАУ иногда удобнее пользоваться методом простой итерации.
Метод итераций для системы уравнений в Excel
На листе Excel организуется таблица в три зоны: первая зона состоит из одного столбца (номер итерации), вторая зона определяет переменные x , третья зона под вычисления точности epsilon .
Во второй зоне по итерационной схеме организуется расчет переменных x (в примере для случая трех переменных):
Итерация №1: =$F$2/$B$2-C6*$C$2/$B$2-D6*$D$2/$B$2;=$F$3/$C$3-B6*$B$3/$C$3-D6*$D$3/$C$3;=$F$4/$D$4-B6*$B$4/$D$4-C6*$C$4/$D$4
Итерация №2: =$F$2/$B$2-C7*$C$2/$B$2-D7*$D$2/$B$2;=$F$3/$C$3-B7*$B$3/$C$3-D7*$D$3/$C$3;=$F$4/$D$4-B7*$B$4/$D$4-C7*$C$4/$D$4
– развитие учебных способностей, умений, навыков и принятия самостоятельных решений в профессиональной деятельности.
Вопросы для изучения:
Цель работы:
формирование навыков по решению систем линейных алгебраических уравнений методом Зейделя в MS Excel.
Методические указания:
1. Изучить предлагаемый вопрос по литературным источникам и предложенной лекции.
2. Составить конспект.
3. Ответить на вопросы для самоконтроля.
Тема: РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ В MS EXCEL. МЕТОД ЗЕЙДЕЛЯ.
1. МЕТОД ЗЕЙДЕЛЯ.
Модификацией метода простых итераций Якоби можно считать метод Зейделя.
В методе Якоби на итерации значения вычисляются подстановкой в правую часть системы:
вычисленных на предыдущей итерации значений
В методе Зейделя при вычислении используются значения уже найденные на итерации, а не как в методе Якоби, т.е. приближение строится следующим образом:
Эти формулы являются расчетными формулами метода Зейделя.
Введем нижнюю и верхнюю треугольные матрицы:
Матричная запись расчетных формул метода Зейделя имеет вид:
Так как точное решение исходной системы удовлетворяет равенству:
Сходимость метода Зейделя. Достаточным условием сходимости метода Зейделя является выполнение неравенства:
Этонеравенство означает, что для сходимости метода Зейделя достаточно, чтобы максимальный по модулю элемент матрицы (полученной из расчётных формул метода Зейделя) был меньше единицы. Если выполнено условие, то справедлива следующая апостериорная оценка погрешности:
где – максимальный элемент матрицы максимальный элемент матрицы .
Правую часть апостериорной оценки погрешности легко вычислить после нахождения очередного приближения.
Критерий окончания. Если требуется найти решение с точностью , то в силу апостериорной оценки погрешности итерационный процесс следует закончить, как только на шаге выполнится неравенство:
Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство:
где
Если выполняется условие то можно пользоваться более простым критерием окончания:
Метод Зейделя, как правило, сходится быстрее, чем метод Якоби. Однако возможны ситуации, когда метод Якоби сходится, а метод Зейделя сходится медленнее или вообще расходится.
Пример:применить метод Зейделя для решения системы линейных алгебраических уравнений
x1 | x2 | x3 | x4 | b | e |
0,79 | -0,12 | 0,34 | 0,16 | -0,64 | 0,001 |
-0,34 | 1,08 | -0,17 | 0,18 | -1,42 | |
-0,16 | -0,34 | 0,85 | 0,31 | -0,42 | |
-0,12 | 0,26 | 0,08 | 0,75 | 0,83 | |
x1 | x2 | x3 | x4 | b | |
1,0000 | -0,1519 | 0,4304 | 0,2025 | -0,8101 | |
-0,3148 | 1,0000 | -0,1574 | 0,1667 | -1,3148 | |
-0,1882 | -0,4000 | 1,0000 | 0,3647 | -0,4941 | |
-0,1600 | 0,3467 | 0,1067 | 1,0000 | 1,1067 | |
B | |||||
x1 | 0,0000 | 0,1519 | -0,4304 | -0,2025 | -0,8101 |
x2 | 0,3148 | 0,0000 | 0,1574 | -0,1667 | -1,3148 |
x3 | 0,1882 | 0,4000 | 0,0000 | -0,3647 | -0,4941 |
x4 | 0,1600 | -0,3467 | -0,1067 | 0,0000 | 1,1067 |
b=maxbij= | 0,4000 | < 1/2 | |||
ответ | |||||
x 0 1= | -0,8101 | x 1 1= | -1,02132 | - | |
x 0 2= | -1,3148 | x 1 2= | -1,89856 | - | |
x 0 3= | -0,4941 | x 1 3= | -1,8494 | - | |
x 0 4= | 1,1067 | x 1 4= | 1,798693 | - | |
x 1 1= | -1,02132 | x 2 1= | -0,66686 | - | |
x 1 2= | -1,89856 | x 2 2= | -2,11565 | - | |
x 1 3= | -1,8494 | x 2 3= | -2,1219 | - | |
x 1 4= | 1,798693 | x 2 4= | 1,959728 | - | |
x 2 1= | -0,66686 | x 3 1= | -0,61518 | - | |
x 2 2= | -2,11565 | x 3 2= | -2,1691 | - | |
x 2 3= | -2,1219 | x 3 3= | -2,19228 | - | |
x 2 4= | 1,959728 | x 3 4= | 1,994038 | - | |
x 3 1= | -0,61518 | x 4 1= | -0,59995 | - | |
x 3 2= | -2,1691 | x 4 2= | -2,18111 | - | |
x 3 3= | -2,19228 | x 4 3= | -2,20673 | - | |
x 3 4= | 1,994038 | x 4 4= | 2,002177 | - | |
x 4 1= | -0,59995 | x 5 1= | -0,59721 | - | |
x 4 2= | -2,18111 | x 5 2= | -2,18388 | - | |
x 4 3= | -2,20673 | x 5 3= | -2,21029 | - | |
x 4 4= | 2,002177 | x 5 4= | 2,003955 | - | |
x 5 1= | -0,59721 | x 6 1= | -0,59646 | Корень | |
x 5 2= | -2,18388 | x 6 2= | -2,1845 | Корень | |
x 5 3= | -2,21029 | x 6 3= | -2,21104 | Корень | |
x 5 4= | 2,003955 | x 6 4= | 2,004371 | Корень | |
Ответ: | x1= | -0,596 | |||
x2= | -2,184 | ||||
x3= | -2,211 | ||||
x4= | 2,004 |
Вопросы для самоконтроля
1. Суть метода итерации Зейделя.
2. Какой из итерационных методов сходится быстрее? Почему?
3. Критерий окончания метода Зейделя.
Список литературы
1. Численные методы: Учебно пособие для студентов вузов ∕ М. П. Лапчик, М. И. Рагулина, Е.К. Хеннер; под ред. М. П. Лапчика. — М.: Издательский центр «Академия», 2004.
2. Численные методы в примерах и задачах: Учебное пособие /В.И. Киреев, А.В. Пантелеев. — 3-е изд. стер. — М.: Высш. шк., 2008.
3. Вычислительная математика в примерах и задачах/ Н. В. Копченова, И. А. Марон. Главная редакция физико-математической литературы изд-ва «Наука», М., 1972.
Модификацией метода простой итерации можно считать метод Зейделя.
В методе простой итерации на -ой итерации значения , вычисляются подстановкой в правую часть (6) вычисленных на предыдущей итерации значений. В методе Зейделя при вычислении используются значения , , , уже найденные на -ой итерации, а не , , …, , как в методе простой итерации, т.е. -е приближение строится следующим образом:
Эти формулы являются расчетными формулами метода Зейделя.
Введем нижнюю и верхнюю треугольные матрицы:
Матричная запись расчетных формул (9) имеет вид: . Так как , точное решение исходной системы удовлетворяет равенству: .
Сходимость метода Зейделя.Достаточным условием сходимости метода Зейделя является выполнение неравенства:
Неравенство (10) означает, что для сходимости метода Зейделя достаточно, чтобы любая норма матрицы был меньше единицы.
Если выполнено условие (10), то справедлива следующая оценка погрешности:
где – норма матрицы.
Критерий окончания. Если требуется найти решение с точностью , итерационный процесс следует закончить, как только на -ом шаге выполнится неравенство: . Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство , где . Если выполняется условие
, то можно пользоваться более простым критерием окончания:
Метод Зейделя, как правило, сходится быстрее, чем метод простой итерации. Однако возможны ситуации, когда метод простой итерации сходится, а метод Зейделя сходится медленнее или вообще расходится.
Пример. Применим метод Зейделя для решения системы уравнений из предыдущего примера. Первые шаги полностью совпадают с процедурой решения по методу простых итераций. Проведем теперь итерации методом Зейделя.
При вычислении используем уже полученное значение :
При вычислении используем уже полученные значения и :
При вычислении используем уже полученные значения , , :
Аналогичным образом проведем вычисления при и .
Известны точные значения переменных:
Сравнение с предыдущим примером показывает, что метод Зейделя сходится быстрее и дает более точный результат.
Читайте также: