Метод зейделя в excel
Обновлено: 03.07.2024
Метод Зейделя представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (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.
Рассмотрим достаточные условия сходимости итерационной последовательности n>.
Практически, для применения метода итерации систему линейных уравнений удобно "погрузить" в одну из трёх следующих метрик:
(3.4)
Для того, чтобы отображение F, заданное в метрическом пространстве соотношениями (3.2), было сжимающим, достаточно выполнение одного из следующих условий:
а) в пространстве с метрикой ρ1: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по строкам, должна быть меньше единицы.
б) в пространстве с метрикой ρ2: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по столбцам, должна быть меньше единицы.
в) в пространстве с метрикой ρ3: , т. е. сумма квадратов при неизвестных в правой части системы (3.2) должна быть меньше единицы
Пример . Вычислить два приближения методом простой итерации. Оценить погрешность второго приближения. В качестве начального приближения выбрать x 0 =(0; 0; 0).
Так как диагональные элементы системы являются преобладающими, то приведем систему к нормальному виду:
Последовательные приближения будем искать по формулам:
При большом числе неизвестных схема метода Гаусса, дающая точное решение, становится весьма сложной. В этом случае для решения СЛАУ иногда удобнее пользоваться методом простой итерации.
Метод итераций для системы уравнений в 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. Критерий окончания метода Зейделя.
Список литературы
2. Численные методы в примерах и задачах: Учебное пособие /В.И. Киреев, А.В. Пантелеев. — 3-е изд. стер. — М.: Высш. шк., 2008.
3. Вычислительная математика в примерах и задачах/ Н. В. Копченова, И. А. Марон. Главная редакция физико-математической литературы изд-ва «Наука», М., 1972.
Модификацией метода простой итерации можно считать метод Зейделя.
В методе простой итерации на -ой итерации значения , вычисляются подстановкой в правую часть (6) вычисленных на предыдущей итерации значений. В методе Зейделя при вычислении используются значения , , , уже найденные на -ой итерации, а не , , …, , как в методе простой итерации, т.е. -е приближение строится следующим образом:
Эти формулы являются расчетными формулами метода Зейделя.
Введем нижнюю и верхнюю треугольные матрицы:
Матричная запись расчетных формул (9) имеет вид: . Так как , точное решение исходной системы удовлетворяет равенству: .
Сходимость метода Зейделя.Достаточным условием сходимости метода Зейделя является выполнение неравенства:
Неравенство (10) означает, что для сходимости метода Зейделя достаточно, чтобы любая норма матрицы был меньше единицы.
Если выполнено условие (10), то справедлива следующая оценка погрешности:
где – норма матрицы.
Критерий окончания. Если требуется найти решение с точностью , итерационный процесс следует закончить, как только на -ом шаге выполнится неравенство: . Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство , где . Если выполняется условие
, то можно пользоваться более простым критерием окончания:
Метод Зейделя, как правило, сходится быстрее, чем метод простой итерации. Однако возможны ситуации, когда метод простой итерации сходится, а метод Зейделя сходится медленнее или вообще расходится.
Пример. Применим метод Зейделя для решения системы уравнений из предыдущего примера. Первые шаги полностью совпадают с процедурой решения по методу простых итераций. Проведем теперь итерации методом Зейделя.
При вычислении используем уже полученное значение :
При вычислении используем уже полученные значения и :
При вычислении используем уже полученные значения , , :
Аналогичным образом проведем вычисления при и .
Известны точные значения переменных:
Сравнение с предыдущим примером показывает, что метод Зейделя сходится быстрее и дает более точный результат.
Этот метод представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (K+1)-го приближения неизвестной XI учитываются уже вычисленные ранее (K+1)-е приближения (X1 X2, . Xi-1).
Пусть дана приведенная линейная система:
(I = 1, 2, …N). (3.35)
Выберем произвольно начальные приближения корней , стараясь, конечно, чтобы они в какой-то мере соответствовали неизвестным X1, x2, x3, . xn.
Предположим, что K-е приближение корней известно, тогда в соответствии с идеей метода будем строить (K+1) – е приближение по следующим формулам:
(3.36)
Обычно процесс Зейделя сходится быстрее, чем метод Якоби. Бывает, что процесс Зейделя сходится, когда простая итерация расходится и, т. п. Правда, бывает и наоборот. Во всяком случае, достаточные условия сходимости для метода Якоби достаточны и для сходимости метода Зейделя. Если выполняется достаточное условие сходимости для системы (3.35) – по строкам, то в методе Зейделя выгодно расположить уравнения (3.36) так, чтобы первое уравнение системы имело наименьшую сумму модулей коэффициентов:
. (3.37)
Для того чтобы обеспечить достаточные условия сходимости итерационного процесса (преобладающие значения диагональных элементов), преобразуем исходную систему и приведем к удобному виду. Чтобы дальнейшие преобразования были понятны, обозначим уравнения исходной системы буквами А, Б, В и Г соответственно:
Х1= -0.2Х2 +0.1Х3 – 0.2Х4 – 0.4; (Г)
Х2 = -0.2Х1 – 0.2Х3 + 0.2; (А – Б)
Х3 = 0.2Х1 – 0.4Х2 + 0.2х4 – 0.4; (Б)
Х4 = 0.333х1 - 1.111. (2А – Б + 2В – Г)
Преобразованную систему будем решать методом Зейделя, тогда, с учетом требования (3.37), окончательно получим:
В качестве нулевого приближения (K = 0) возьмем . Зададим количество итераций K = 2 и все результаты вычислений сведем в табл. 3.1.
Читайте также: