Метод Якоби

Метод Якоби

Метод Якобиметод простой итерации для решения системы линейных алгебраических уравнений.

Содержание

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

Возьмём систему линейных уравнений:

A\vec{x}=\vec{b}, где A=\left(
\begin{array}{ccc}
a_{11} & \ldots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \ldots & a_{nn} 
\end{array} \right),\quad \vec{b}=\left(
\begin{array}{c}
b_1 \\
\vdots \\
b_n 
\end{array} \right)

Или \left\{
\begin{array}{rcl}
a_{11}x_1 + \ldots + a_{1n}x_n& = & b_{1} \\
\ldots ~~~~~~~~~~~~~~~~~~~~~ \\
a_{n1}x_1 + \ldots + a_{nn}x_n & = & b_{n} 
\end{array} \right.

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

Для того, чтобы построить итеративную процедуру метода Якоби, необходимо провести предварительное преобразование системы уравнений A\vec{x}=\vec{b} к итерационному виду \vec{x}=B\vec{x}+\vec{g}. Оно может быть осуществлено по одному из следующих правил:

  • B = E-D^{-1}A = D^{-1}(D - A),\quad \vec{g}=D^{-1}\vec{b};
  • B = -D^{-1}(L + U) = -D^{-1}(A - D),\quad \vec{g}=D^{-1}\vec{b}
  • D^{-1}_{ii} = 1 / D_{ii}, D_{ii} \neq 0,\, i = 1,2, ..., n\quad;


где в принятых обозначениях D означает матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы A, а все остальные нули; тогда как матрицы U и L содержат верхнюю и нижнюю треугольные части A, на главной диагонали которых нули, Eединичная матрица.

Тогда процедура нахождения решения имеет вид:

 \vec{x}^{(k+1)}  = B \vec{x}^{(k)}+\vec{g},

Или в виде поэлементной формулы:

 x^{(k+1)}_i  = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k)}_j\right),\quad i=1,2,\ldots,n.

где k счётчик итерации.

В отличие от метода Гаусса-Зейделя мы не можем заменять x^{(k)}_i\, на x^{(k+1)}_i в процессе итерационной процедуры, т.к. эти значения понадобятся для остальных вычислений. Это наиболее значимое различие между методом Якоби и методом Гаусса-Зейделя решения СЛАУ. Таким образом на каждой итерации придётся хранить оба вектора приближений: старый и новый.

Условие сходимости

Приведем достаточное условие сходимости метода.

Logo arte.jpg Теорема.
Пусть \| B \| < 1\!. Тогда при любом выборе начального приближения \vec{x}^{(0)}\!:
  1. метод сходится;
  2. скорость сходимости метода равна скорости сходимости геометрической прогрессии со знаменателем q= \|B\|\!;
  3. верна оценка погрешности: \|\vec{x}^{(k)}-\vec{x}\| < q^k \, \|\vec{x}^{(0)}-\vec{x}\|\!.

Условие остановки

Условие окончания итерационного процесса при достижении точности \varepsilon в упрощённой форме имеет вид:

max_j\|x_j^{(k+1)}-x_j^{(k)}\|/(1-q) < \varepsilon\!

(Существует более точное условие окончания итерационного процесса, которое более сложно и требует дополнительных вычислений)[источник не указан 725 дней]


Алгоритм

Ниже приведён алгоритм реализации на C++

#include <math.h>
const double eps = 0.001; ///< желаемая точность 
 
..........................
 
/// N - размерность матрицы; A[N][N] - матрица коэффициентов, F[N] - столбец свободных членов,
/// X[N] - начальное приближение, ответ записывается также в X[N];
void Jacobi (int N, double **A, double *F, double *X)
{
        double * TempX = new double[N];
        double norm; // норма, определяемая как наибольшая разность компонент столбца иксов соседних итераций.
 
        do {
                for (int i = 0; i < N; i++) {
                        TempX[i] =- F[i];
                        for (int g = 0; g < N; g++) {
                                if (i != g)
                                        TempX[i] += A[i][g] * X[g];
                        }
                        TempX[i] /= -A[i][i];
                }
                norm = fabs(X[0] - TempX[0]);
                for (int h = 0; h < N; h++) {
                        if (fabs(X[h] - TempX[h]) > norm)
                                norm = fabs(X[h] - TempX[h]);
                        X[h] = TempX[h];
                }
        } while (norm > eps);
        delete[] TempX;
}

См. также



Wikimedia Foundation. 2010.

Поможем написать реферат

Полезное


Смотреть что такое "Метод Якоби" в других словарях:

  • Метод Якоби для собственных значений — У этого термина существуют и другие значения, см. Метод Якоби. В линейной алгебре метод Якоби для собственных значений  итерационный метод для вычисления собственных значений и собственных векторов вещественной симметричной матрицы. Он… …   Википедия

  • Метод Якоби для линейных систем — У этого термина существуют и другие значения, см. Метод Якоби. Метод Якоби метод простой итерации для решения системы линейных алгебраических уравнений. Содержание 1 Постановка задачи 2 Описание метода …   Википедия

  • Метод Гаусса — Зейделя — У этого термина существуют и другие значения, см. метод покоординатного спуска. Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод …   Википедия

  • Метод Гаусса-Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости …   Википедия

  • Метод Гаусса—Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости …   Википедия

  • Метод Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости …   Википедия

  • Якоби, Карл Густав Якоб — В Википедии есть статьи о других людях с такой фамилией, см. Якоби. Карл Густав Якоб Якоби Carl Gustav Jacob Jacobi …   Википедия

  • Якоби, Карл Густав Яков — Карл Густав Якоб Якоби Carl Gustav Jacob Jacobi Дата рождения: 10 декабря 1804 Место рождения: Потсдам Дата смерти: 18 февраля 1851 Место смерти …   Википедия

  • Якоби Карл Густав Якоб — Карл Густав Якоб Якоби Carl Gustav Jacob Jacobi Дата рождения: 10 декабря 1804 Место рождения: Потсдам Дата смерти: 18 февраля 1851 Место смерти …   Википедия

  • Якоби Карл Густав Яков — Карл Густав Якоб Якоби Carl Gustav Jacob Jacobi Дата рождения: 10 декабря 1804 Место рождения: Потсдам Дата смерти: 18 февраля 1851 Место смерти …   Википедия

Книги

  • Vorlesungen uber Dynamik, C. G. J. Jacobi. Берлин, 1884 год. Издательство "Druck und Verlag von Georg Dreimer" . Владельческий переплет. Кожаный корешок и уголки. Корешок бинтовой. Сохранность хорошая. Вниманию читателя предлагается… Подробнее  Купить за 7980 руб
  • Лекции по динамике., Якоби К.. Предметом настоящих лекций будет исследование тех преимуществ, которые можно извлечь при интегрировании дифференциальных уравнении движения из особой формы этихуравнений. В Аналитической… Подробнее  Купить за 1723 грн (только Украина)
  • Лекции по динамике., Якоби К.. Предметом настоящих лекций будет исследование тех преимуществ, которые можно извлечь при интегрировании дифференциальных уравнении движения из особой формы этих уравнений. В Аналитической… Подробнее  Купить за 1532 руб
Другие книги по запросу «Метод Якоби» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»