рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Метод Зейделя - раздел Математика, Вычислительные методы линейной алгебры Пусть Требуется Решить Систему Уравнений (3.1):   ...

Пусть требуется решить систему уравнений (3.1):

 

(3.25)

 

Выразим из первого уравнения переменную x1, из второго — x2, и т.д.:

Пусть k-е приближение к решению обозначено так . Подставим его в правую часть полученной системы и выразим следующее приближение . В отличие от метода итераций, метод Зейделя использует при вычислении уже найденные компоненты вектора xk+1.

Расчетные формулы метода Зейделя можно записать в виде:

 

(3.26)

 

Теорема 3.3 (достаточные условия сходимости [1]). Пусть при всех i для коэффициентов системы уравнений (3.25) выполняются условия

 

(3.27)

 

Тогда метод Зейделя сходится и выполняется неравенство

 

, (3.28)

 

где x* — точное решение системы (3.25).

Если матрица A удовлетворяет условию (3.27), то говорят, что A — матрица с диагональным преобладанием.

Пример 3.5. Решить систему уравнений методом итераций и методом Зейделя. Сравнить скорости сходимости методов.

 

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

 

и запишем расчетные формулы метода Зейделя

 

 

Введем в программе Excel обозначения в ячейках A1:D1, начальные значения в ячейках B2:D2 и формулы в ячейках B3:D3, как показано в таблице 3.4. Выделим диапазон B3:D3 и протянем маркер заполнения вниз до ячейки D12. Для нумерации последовательных приближений выделим диапазон A2:A3 и протянем маркер заполнения вниз до ячейки A12. Получим 10 последовательных приближений к решению.

Таблица 3.4

  A B C D E
k X1 X2 X3 Погрешность
 
=(5-2*C2-D2)/9 =(6+B3+D2)/7 =(-3-B3-C3)/9 =МАКС(ABS(B3-B2); ABS(C3-C2); ABS(D3-D2))

 

Результаты расчетов приведены в таблице 3.5. Как видим, есть сходимость процесса итераций, так как соответствующие компоненты векторов x9 и x10 содержат по 8 одинаковых значащих цифр, начиная слева направо. Норма разности ||x10x9||1 = 3,92663E–10 < 0,000000001.

Таблица 3.5

  A B C D E
k X1 X2 X3 Погрешность
 
0,222222222 1,031746032 -0,472663139 1,472663139
0,378796786 0,843733378 -0,469170018 0,188012654
0,420189251 0,850145605 -0,474481651 0,041392465
0,419354493 0,849267549 -0,474291338 0,000878056
0,419528471 0,84931959 -0,474316451 0,000173978
0,419519697 0,849314749 -0,474314938 8,77441E-06
0,419520604 0,849315095 -0,474315078 9,07706E-07
0,419520543 0,849315066 -0,474315068 6,13672E-08
0,419520548 0,849315069 -0,474315069 5,25818E-09
0,419520548 0,849315068 -0,474315068 3,92663E-10

 

Приведем результаты решения системы методом итераций. Если в таблице 3.4 формулы в третьей строке заменить на формулы метода итераций, как показано в ячейках A3:D3 таблицы 3.6, затем выделить A3:D3 и скопировать вниз маркером заполнения до строки 12, то получим таблицу 3.7.

Таблица 3.6

  A B C D E
k X1 X2 X3 Погрешность
 
=(5-2*C2-D2)/9 =(6+B2+D2)/7 =(-3-B2-C2)/9 =МАКС(ABS(B3-B2); ABS(C3-C2); ABS(D3-D2))

 

Сравнивая таблицы 3.5 и 3.7, мы видим, что метод Зейделя имеет более высокую скорость сходимости, чем метод итераций. Например, на шаге k = 4, метод итераций дает погрешность 0,012514, а метод Зейделя имеет на этом же шаге погрешность 0,000878056.

Таблица 3.7

  A B C D E
k X1 X2 X3 Погрешность
 
0,222222 1,142857 -0,55556 1,555556
0,363316 0,809524 -0,48501 0,333333
0,429551 0,839758 -0,46365 0,066236
0,420459 0,852272 -0,47437 0,012514
0,418869 0,849442 -0,47475 0,00283
0,419541 0,84916 -0,47426 0,000671
0,419548 0,849326 -0,4743 0,000166
0,419516 0,849321 -0,47432 3,21E-05
0,41952 0,849314 -0,47432 7,35E-06
0,419521 0,849315 -0,47431 1,17E-06

 

 

Теорема 3.4(достаточные условия сходимости [1]).Пусть матрица A системы (3.1) — вещественная, симметричная и положительно определенная. Тогда метод Зейделя сходится.

Пример 3.6.Решить методом Зейделя систему уравнений

 

 

Решение.Матрица системы симметрична, но не имеет диагонального преобладания.Применяя критерий Сильвестра (см. ниже п. 3.6, теорема 3.8), покажем, что матрица системы положительно определена:

 

 

Согласно теореме 3.4 метод Зейделя для данной системы сходится. Выразим из каждого уравнения соответствующую переменную и запишем формулы метода Зейделя:

 

 

Аналогично примеру 3.5 по данным расчетным формулам можно вычислить решение системы линейных уравнений.

Составим программу на языке C++ для решения системы уравнений методом Зейделя (3.26):

 

#include <except.h>

#include <iostream.h>

#include <math.h>

int Zeidel(long double **a, long double *b, long double *x,

long double eps, int k_max, const int n);

int main(){

long double **a; long double *b, *x, eps; int i,j,n,k_max;

cout <<" input n = " ; cin >> n;

cout <<" input eps = " ; cin >> eps;

cout <<" input k_max = " ; cin >> k_max;

try {

a= new long double*[n]; for(i=0;i<n;i++) a[i]=new long double[n];

b= new long double[n]; x= new long double[n];

}

catch (xalloc){cout <<" Could not allocate "; exit(-1);}

cout <<" input matrix a ";

for (i=0; i<n; i++)for (j=0; j<n; j++)cin >> a[i][j];

cout <<" input vector b ";

for (i=0; i<n; i++)cin >> b[i];

cout << " matrix a: ";

for (i=0; i<n; i++){cout << " "; for (j=0; j<n; j++) cout <<" "<< a[i][j];}

cout << " vector b: ";

for (i=0; i<n; i++)cout << " " << b[i];

Zeidel(a, b, x,eps,k_max, n);

cout << " vector x: ";

for (i=0; i<n; i++)cout << " x[" << i <<"] = " << x[i];

cout << " Press Key and Enter to continue";

cin >> i; // for pause

for(i=0;i<n;i++)delete[] a[i];

delete a;

delete[] b;

delete[] x;

return 0;

}//end main

int Zeidel(long double **a, long double *b, long double *x,

long double eps, int k_max, const int n){

int i, j, m; long double *x1, xerr, s;

try {x1 = new long double[n];}

catch (xalloc){cout <<" Could not allocate "; exit(-1);}

for (i = 0; i < n; i++)x1[i] = x[i];

for (m = 0; m <= k_max; m++) {// m

for (i = 0; i < n; i++){ //i

s = b[i];

for (j = 0; j < n ; j++) if(j != i)s = s - a[i][j]*x1[j];

x1[i] = s / a[i][i];}//end i

xerr = 0;

for (i = 0; i < n; i++) xerr = xerr + (x1[i] - x[i])* (x1[i] - x[i]);

xerr = sqrt(xerr); for (i = 0; i < n; i++)x[i] = x1[i];

if(xerr < eps) break;

}// end m

delete[] x1;

return 0;

}// end iter

 

Найдем с помощью этой программы решение системы уравнений примера 3.4:

 

input n = 3

input eps = 0.0000001

input k_max = 10000

input matrix a

4 –2 0 –2 4 –2 0 –2 4

Input vector c

5 –6 –3

matrix a:

4 –2 0

–2 4 –2

0 –2 4

vector 5:

–6

–3

vector x:

x[0] = 4.84288e–08

x[1] = –2.5

x[2] = –2

Press Key and Enter to continue

 

Ответ: x = (0; –2,5; –2).

– Конец работы –

Эта тема принадлежит разделу:

Вычислительные методы линейной алгебры

Вычислительные методы линейной алгебры изучают численные методы решения следующих задач... Решить систему линейных алгебраических уравнений СЛАУ... Вычислить определитель квадратной матрицы A...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Метод Зейделя

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Нормы векторов и матриц
Приведем определения норм векторов и матриц [1]. Пусть задан вектор x= (x1, x2, …, xn)T. Наиболее час

Решение систем линейных алгебраических уравнений
Теоретические условия существования и единственности решения систем линейных уравнений известны — главный определитель не должен быть равен нулю. Тогда решение можно найти по правилу Крамера

Метод Гаусса для решения систем линейных уравнений
Пусть требуется решить систему n линейных алгебраических уравнений с n неизвестными:  

Алгоритм метода Гаусса с выбором главного элемента по столбцам.
1. Для m = 1, 2, …, n – 1 выполним преобразования: Найдем максимальный по абсолютной величине элемент в m-ом столбце. Пусть это будет элемент aim. Ес

Итерационный метод
Запишем систему уравнений (3.9) в виде   Ax = b, (3.21) где A — матрица коэффициентов, а b

Погрешность решения и обусловленность системы уравнений
Рассмотрим влияние погрешности правой части и свойств матрицы системы линейных уравнений на погрешность решения. Пусть правая часть системы задана приближенно, с погрешностью η:  

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

Собственные числа и собственные векторы матрицы
Приведем основные определения и теоремы, необходимые для решения практических задач вычисления собственных чисел и собственных векторов матриц. Определение 3.5. Собственны

Алгоритм определения наибольшего по модулю собственного значения и соответствующего собственного вектора матрицы с положительными элементами.
1. Зададим начальное приближение x0 к собственному вектору; k = 0; 2. Вычисляем следующие приближения xk

Метод скалярных произведений
Рассмотрим метод скалярных произведений [7] для определения наибольшего собственного значения и соответствующего собственного вектора действительной матрицы A. Теорема 3.10.

Алгоритм метода скалярных произведений.
1. Зададим начальные приближения: x0 — к собственному вектору матрицы A и y0 = x0 — к

Алгоритм вычисления очередного (m + 1)-го собственного значения и соответствующего собственного вектора.
0. Выберем начальное приближение ; k = 0; 1. Вычисляем k-е прибл

Задачи для самостоятельного решения.
Решить систему линейных уравнений Ax = b в электронных таблицах методом Гаусса. Вычислить определитель матрицы A методом Гаусса. Найти обратну

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги