Методы решения слау

Определение системы линейных алгебраических уравнений. Решение системы. Классификация систем.

Под системой линейных алгебраических уравнений (СЛАУ) подразумевают систему

\begin{equation} \left \{ \begin{aligned} & a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_n=b_1;\\ & a_{21}x_1+a_{22}x_2+a_{23}x_3+\ldots+a_{2n}x_n=b_2;\\ & \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \\ & a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\ldots+a_{mn}x_n=b_m. \end{aligned} \right. \end{equation}

содержащую $m$ уравнений и $n$ неизвестных ($x_1,x_2,\ldots,x_n$). Прилагательное «линейных» означает, что все неизвестные (их еще называют переменными) входят только в первой степени.

Параметры $a_{ij}$ ($i=\overline{1,m}$, $j=\overline{1,n}$) называют коэффициентами, а $b_i$ ($i=\overline{1,m}$) – свободными членами СЛАУ. Иногда, чтобы подчеркнуть количество уравнений и неизвестных, говорят так «$m\times n$ система линейных уравнений», – тем самым указывая, что СЛАУ содержит $m$ уравнений и $n$ неизвестных.

Если все свободные члены $b_i=0$ ($i=\overline{1,m}$), то СЛАУ называют однородной. Если среди свободных членов есть хотя бы один, отличный от нуля, СЛАУ называют неоднородной.

Решением СЛАУ (1) называют всякую упорядоченную совокупность чисел ($\alpha_1, \alpha_2,\ldots,\alpha_n$), если элементы этой совокупности, подставленные в заданном порядке вместо неизвестных $x_1,x_2,\ldots,x_n$, обращают каждое уравнение СЛАУ в тождество.

Любая однородная СЛАУ имеет хотя бы одно решение: нулевое (в иной терминологии – тривиальное), т.е. $x_1=x_2=\ldots=x_n=0$.

Если СЛАУ (1) имеет хотя бы одно решение, ее называют совместной, если же решений нет – несовместной. Если совместная СЛАУ имеет ровно одно решение, её именуют определённой, если бесконечное множество решений – неопределённой.

Пример №1

Рассмотрим СЛАУ

\begin{equation} \left \{ \begin{aligned} & 3x_1-4x_2+x_3+7x_4-x_5=11;\\ & 2x_1+10x_4-3x_5=-65;\\ & 3x_2+19x_3+8x_4-6x_5=0. \\ \end {aligned} \right. \end{equation}

Имеем систему линейных алгебраических уравнений, содержащую $3$ уравнения и $5$ неизвестных: $x_1,x_2,x_3,x_4,x_5$. Можно, сказать, что задана система $3\times 5$ линейных уравнений.

Коэффициентами системы (2) есть числа, стоящие перед неизвестными.

Например, в первом уравнении эти числа таковы: $3,-4,1,7,-1$. Свободные члены системы представлены числами $11,-65,0$. Так как среди свободных членов есть хотя бы один, не равный нулю, то СЛАУ (2) является неоднородной.

Упорядоченная совокупность $(4;-11;5;-7;1)$ является решением данной СЛАУ. В этом несложно убедиться, если подставить $x_1=4; x_2=-11; x_3=5; x_4=-7; x_5=1$ в уравнения заданной системы:

\begin{aligned} & 3x_1-4x_2+x_3+7x_4-x_5=3\cdot4-4\cdot(-11)+5+7\cdot(-7)-1=11;\\ & 2x_1+10x_4-3x_5=2\cdot 4+10\cdot (-7)-3\cdot 1=-65;\\ & 3x_2+19x_3+8x_4-6x_5=3\cdot (-11)+19\cdot 5+8\cdot (-7)-6\cdot 1=0. \\ \end{aligned}

Естественно, возникает вопрос том, является ли проверенное решение единственным. Вопрос о количестве решений СЛАУ будет затронут в соответствующей теме.

Пример №2

Рассмотрим СЛАУ

\begin{equation} \left \{ \begin{aligned} & 4x_1+2x_2-x_3=0;\\ & 10x_1-x_2=0;\\ & 5x_2+4x_3=0; \\ & 3x_1-x_3=0;\\ & 14x_1+25x_2+5x_3=0. \end{aligned} \right. \end{equation}

Система (3) является СЛАУ, содержащей $5$ уравнений и $3$ неизвестных: $x_1,x_2,x_3$. Так как все свободные члены данной системы равны нулю, то СЛАУ (3) является однородной. Несложно проверить, что совокупность $(0;0;0)$ является решением данной СЛАУ. Подставляя $x_1=0, x_2=0,x_3=0$, например, в первое уравнение системы (3), получим верное равенство: $4x_1+2x_2-x_3=4\cdot 0+2\cdot 0-0=0$. Подстановка в иные уравнения делается аналогично.

Матричная форма записи систем линейных алгебраических уравнений.

С каждой СЛАУ можно связать несколько матриц; более того – саму СЛАУ можно записать в виде матричного уравнения. Для СЛАУ (1) рассмотрим такие матрицы:

Матрица $A$ называется матрицей системы. Элементы данной матрицы представляют собой коэффициенты заданной СЛАУ.

Матрица $\widetilde{A}$ называется расширенной матрицей системы. Её получают добавлением к матрице системы столбца, содержащего свободные члены $b_1,b_2,…,b_m$. Обычно этот столбец отделяют вертикальной чертой, – для наглядности.

Матрица-столбец $B$ называется матрицей свободных членов, а матрица-столбец $X$ – матрицей неизвестных.

Используя введённые выше обозначения, СЛАУ (1) можно записать в форме матричного уравнения: $A\cdot X=B$.

Примечание

Матрицы, связанные с системой, можно записать различными способами: всё зависит от порядка следования переменных и уравнений рассматриваемой СЛАУ. Но в любом случае порядок следования неизвестных в каждом уравнении заданной СЛАУ должен быть одинаков (см. пример №4).

Пример №3

Записать СЛАУ $ \left \{ \begin{aligned} & 2x_1+3x_2-5x_3+x_4=-5;\\ & 4x_1-x_3=0;\\ & 14x_2+8x_3+x_4=-11. \end{aligned} \right. $ в матричной форме и указать расширенную матрицу системы.

Решение

Имеем четыре неизвестных, которые в каждом уравнении следуют в таком порядке: $x_1,x_2,x_3,x_4$. Матрица неизвестных будет такой: $\left( \begin{array} {c} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right)$.

Свободные члены данной системы выражены числами $-5,0,-11$, посему матрица свободных членов имеет вид: $B=\left( \begin{array} {c} -5 \\ 0 \\ -11 \end{array} \right)$.

Перейдем к составлению матрицы системы. В первую строку данной матрицы будут занесены коэффициенты первого уравнения: $2,3,-5,1$.

Во вторую строку запишем коэффициенты второго уравнения: $4,0,-1,0$. При этом следует учесть, что коэффициенты системы при переменных $x_2$ и $x_4$ во втором уравнении равны нулю (ибо эти переменные во втором уравнении отсутствуют).

В третью строку матрицы системы запишем коэффициенты третьего уравнения: $0,14,8,1$. Учитываем при этом равенство нулю коэффициента при переменной $x_1$(эта переменная отсутствует в третьем уравнении). Матрица системы будет иметь вид:

$$ A=\left( \begin{array} {cccc} 2 & 3 & -5 & 1\\ 4 & 0 & -1 & 0 \\ 0 & 14 & 8 & 1 \end{array} \right) $$

Чтобы была нагляднее взаимосвязь между матрицей системы и самой системой, я запишу рядом заданную СЛАУ и ее матрицу системы:

В матричной форме заданная СЛАУ будет иметь вид $A\cdot X=B$. В развернутой записи:

$$ \left( \begin{array} {cccc} 2 & 3 & -5 & 1\\ 4 & 0 & -1 & 0 \\ 0 & 14 & 8 & 1 \end{array} \right) \cdot \left( \begin{array} {c} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right) = \left( \begin{array} {c} -5 \\ 0 \\ -11 \end{array} \right) $$

Запишем расширенную матрицу системы. Для этого к матрице системы $ A=\left( \begin{array} {cccc} 2 & 3 & -5 & 1\\ 4 & 0 & -1 & 0 \\ 0 & 14 & 8 & 1 \end{array} \right) $ допишем столбец свободных членов (т.е. $-5,0,-11$). Получим: $\widetilde{A}=\left( \begin{array} {cccc|c} 2 & 3 & -5 & 1 & -5 \\ 4 & 0 & -1 & 0 & 0\\ 0 & 14 & 8 & 1 & -11 \end{array} \right) $.

Пример №4

Записать СЛАУ $ \left \{\begin{aligned} & 3y+4a=17;\\ & 2a+4y+7c=10;\\ & 8c+5y-9a=25; \\ & 5a-c=-4. \end{aligned}\right.$ в матричной форме и указать расширенную матрицу системы.

Решение

Как видите, порядок следования неизвестных в уравнениях данной СЛАУ различен. Например, во втором уравнении порядок таков: $a,y,c$, однако в третьем уравнении: $c,y,a$. Перед тем, как записывать СЛАУ в матричной форме, порядок следования переменных во всех уравнениях нужно сделать одинаковым.

Упорядочить переменные в уравнениях заданной СЛАУ можно разными способами (количество способов расставить три переменные составит $3!=6$). Я разберу два способа упорядочивания неизвестных.

Способ №1

Введём такой порядок: $c,y,a$. Перепишем систему, расставляя неизвестные в необходимом порядке: $\left \{\begin{aligned} & 3y+4a=17;\\ & 7c+4y+2a=10;\\ & 8c+5y-9a=25; \\ & -c+5a=-4. \end{aligned}\right.$

Для наглядности я запишу СЛАУ в таком виде: $\left \{\begin{aligned} & 0\cdot c+3\cdot y+4\cdot a=17;\\ & 7\cdot c+4\cdot y+2\cdot a=10;\\ & 8\cdot c+5\cdot y-9\cdot a=25; \\ & -1\cdot c+0\cdot y+5\cdot a=-4. \end{aligned}\right.$

Матрица системы имеет вид: $ A=\left( \begin{array} {ccc} 0 & 3 & 4 \\ 7 & 4 & 2\\ 8 & 5 & -9 \\ -1 & 0 & 5 \end{array} \right) $. Матрица свободных членов: $B=\left( \begin{array} {c} 17 \\ 10 \\ 25 \\ -4 \end{array} \right)$. При записи матрицы неизвестных помним о порядке следования неизвестных: $X=\left( \begin{array} {c} c \\ y \\ a \end{array} \right)$. Итак, матричная форма записи заданной СЛАУ такова: $A\cdot X=B$. В развёрнутом виде:

$$ \left( \begin{array} {ccc} 0 & 3 & 4 \\ 7 & 4 & 2\\ 8 & 5 & -9 \\ -1 & 0 & 5 \end{array} \right) \cdot \left( \begin{array} {c} c \\ y \\ a \end{array} \right) = \left( \begin{array} {c} 17 \\ 10 \\ 25 \\ -4 \end{array} \right) $$

Расширенная матрица системы такова: $\left( \begin{array} {ccc|c} 0 & 3 & 4 & 17 \\ 7 & 4 & 2 & 10\\ 8 & 5 & -9 & 25 \\ -1 & 0 & 5 & -4 \end{array} \right) $.

Способ №2

Введём такой порядок: $a,c,y$. Перепишем систему, расставляя неизвестные в необходимом порядке: $\left \{ \begin{aligned} & 4a+3y=17;\\ & 2a+7c+4y=10;\\ & -9a+8c+5y=25; \\ & 5a-c=-4. \end{aligned}\right.$

Для наглядности я запишу СЛАУ в таком виде: $\left \{ \begin{aligned} & 4\cdot a+0\cdot c+3\cdot y=17;\\ & 2\cdot a+7\cdot c+4\cdot y=10;\\ & -9\cdot a+8\cdot c+5\cdot y=25; \\ & 5\cdot c-1\cdot c+0\cdot y=-4. \end{aligned}\right.$

Матрица системы имеет вид: $ A=\left( \begin{array} {ccc} 4 & 0 & 3 \\ 2 & 7 & 4\\ -9 & 8 & 5 \\ 5 & -1 & 0 \end{array} \right)$. Матрица свободных членов: $B=\left( \begin{array} {c} 17 \\ 10 \\ 25 \\ -4 \end{array} \right)$. При записи матрицы неизвестных помним о порядке следования неизвестных: $X=\left( \begin{array} {c} a \\ c \\ y \end{array} \right)$. Итак, матричная форма записи заданной СЛАУ такова: $A\cdot X=B$. В развёрнутом виде:

$$ \left( \begin{array} {ccc} 4 & 0 & 3 \\ 2 & 7 & 4\\ -9 & 8 & 5 \\ 5 & -1 & 0 \end{array} \right) \cdot \left( \begin{array} {c} a \\ c \\ y \end{array} \right) = \left( \begin{array} {c} 17 \\ 10 \\ 25 \\ -4 \end{array} \right) $$

Решение СЛАУ методом LU-разложения по Алгоритму Краута

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

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

Понятие LU-разложение

Представление матрицы A в виде произведения двух матриц, A = L * U, где L — нижняя треугольная матрица, а U — верхняя треугольная матрица.

$L=\left$ $U=\left$

Матрица — математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля (например, целых, действительных или комплексных чисел), которая представляет собой совокупность строк и столбцов, на пересечении которых находятся её элементы.

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

$$L * U * x = y$$

т.е.

$$A = L * U$$

Причем для определенности полагается, что матрица L является нижнетреугольной, а U–верхнетреугольной, причем с единичной диагональю.

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

\begin{equation*} {\Delta}=\prod _{i=1}^{n}{{l}_{11}} \end{equation*} Ограничившись для наглядности порядком n = 4, запишем L- и U-матрицы:

Применения

Решение систем алгебраических линейных уравнений

Полученное LU-разложение матрицы A (матрица коэффициентов системы) может быть использовано для решения семейства систем линейных уравнений с различными векторами b в правой части:

$$A * x = b$$

Если известно LU-разложение матрицы A, $$A = L*U$$, исходная система может быть записана как

$$L * U * x = b,$$

Эта система может быть решена в два шага. На первом шаге решается система

$$L * U = b,$$ Поскольку I — нижняя треугольная матрица, эта система решается непосредственно прямой подстановкой. На втором шаге решается система $$U * x = y,$$

Поскольку U — верхняя треугольная матрица, эта система решается непосредственно обратной подстановкой.

Обращение матриц

Обращение матрицы A эквивалентно решению линейной системы

$$A * X = I$$

где X — неизвестная матрица, I — единичная матрица. Решение X этой системы является обратной матрицей ${A}^{-1}$. Систему можно решить описанным выше методом LU-разложения.

Вычисление определителя матрицы

Определитель (или детерминант) – это многочлен, комбинирующий элементы квадратной матрицы таким образом, что его значение сохраняется при транспонировании и линейных комбинациях строк или столбцов. То есть, определитель характеризует содержание матрицы. В частности, если в матрице есть линейно-зависимые строки или столбцы, — определитель равен нулю.

Определитель играет ключевую роль в решении в общем виде систем линейных уравнений, на его основе вводятся базовые понятия. Имея LU-разложение матрицы A,

$$A=L*U,$$ можно непосредственно вычислить её определитель, \begin{equation*} \mathit{det}\left(A\right)=\mathit{det}\left(\mathit{LU}\right)=\mathit{det}\left(L\right)\mathit{det}\left(U\right)=\left(\prod _{i=1}^{n}{\mathit{Lii}}\right)\left(\prod _{i=1}^{n}{\mathit{Uii}}\right) \end{equation*} где n — размер матрицы A, $l_{ii}$ и $u_{ii}$ — диагональные элементы матриц L и U.

Алгоритм Краута

Суть алгоритма Краута. Предполагая, что разложение A = L * U существует, запишем произведение L * U:

A = \begin{bmatrix}l_{11} & l_{11} u_{12} & l_{11} u_{12} & l_{11} u_{14} \\ l_{21} & l_{21} u_{12} + l_{22} & l_{21} u_{13} + l_{22} u_{23} & l_{21} u_{14} + l_{22} u_{24} \\ l_{31} & l_{31} u_{12} + l_{32} & l_{31} u_{13} + l_{32} u_{23} + l_{33} & l_{31} u_{14} + l_{32} u_{24} + l_{33} u_{34} \\ l_{41} & l_{41} u_{12} + l_{42} & l_{41} u_{13} + l_{42} u_{23} + l_{43} & l_{41} u_{14} + l_{42} u_{24} + l_{34} u_{34} + l_{44}\end{bmatrix}

Сравнивая компоненты этого произведения с компонентами матрицы A, видим, что первый столбец произведения L * U равен первому столбцу матрицы A, т.е. , при i = 1,…,4. Первая строка произведения может быть использована для определения первой строки матрицы U.

Действительно, т.к.

$$l_{11}*u_{1j}=a_{1j},$$ при j=2,..4, получаем $$u_{1j}=a_{1j}/a_{11}.$$ Поскольку во втором столбце элементы $u_{12}$ и $l_{i3}$ известны, можем определить второй столбец матрицы L: \begin{equation*} {l}_{\mathit{i2}}={a}_{12}-{l}_{\mathit{i1}}\ast {u}_{12} \end{equation*}

где $i=2,…,4$. Теперь, т.к. известны $l_{21}$ , $l_{22}$ и $u_{1j}$, можно по второй строке произведения определить вторую строку матрицы U:

\begin{equation*} {u}_{2j}=\left({a}_{2j}-{l}_{21}\ast {u}_{1j}\right)/{{l}_{22}} \end{equation*}

при $j=3,…,4$. Далее, чередуя строки и столбцы, можно аналогичным образом найти остальные элементы матриц L и U. Чтобы получить общие соотношения, запишем произвольный элемент произведения L * U:

Чтобы получить общие соотношения, запишем произвольный элемент произведения L * U:

\begin{equation*} {a}_{\mathit{ij}}=\sum _{m=1}^{n}{{l}_{\Im }\ast {u}_{\mathit{mj}}=\sum _{m=1}^{\mathit{min}\text(i,j)}{{l}_{\Im }\ast {u}_{\mathit{mj}}}} \end{equation*}

где верхний предел суммы учитывает наличие нулевых элементов в матрицах L и U. Рассмотрим произвольный элемент на или под главной диагональю матрицы A, для которого , и заменим индекс на . Учитывая при этом, что $u_{kk} = 1$, получим

\begin{equation*} {a}_{\mathit{ik}}=\sum _{m=1}^{k}{{l}_{\Im }\ast {u}_{\mathit{mk}}}={l}_{\mathit{ik}}+\sum _{m=1}^{k-1}{{l}_{\Im }\ast {u}_{\mathit{mk}}} \end{equation*}

откуда

\begin{equation*} {l}_{\mathit{ik}}={a}_{\mathit{ik}}-\sum _{m=1}^{k-1}{{l}_{\Im }\ast {u}_{\mathit{mk}}},(1.1) \end{equation*}

при $j>=k$ и $k=1,..,n$. Аналогичным образом, рассматривая произвольный элемент над главной диагональю, для которого , и используя k вместо i, находим

\begin{equation*} {a}_{\mathit{kj}}=\sum _{m=1}^{k}{{l}_{\mathit{mk}}\ast {u}_{\mathit{mj}}}={l}_{\mathit{ik}}\ast {u}_{\mathit{kj}}+\sum _{m=1}^{k-1}{{l}_{\mathit{km}}\ast {u}_{\mathit{mj}}} \end{equation*}

откуда

\begin{equation*} {u}_{\mathit{kj}}=\left({a}_{\mathit{kj}}-\sum _{m=1}^{k-1}{{l}_{\mathit{km}}}\ast {u}_{\mathit{mj}}\right)/{{l}_{\mathit{kk},(1.2)}} \end{equation*}

при и j > k, и k = 1,…,n.

Эти соотношения для $l_{ik}$ и $u_{kj}$ есть алгоритм разложения на треугольные матрицы – алгоритм Краута. Заметим, что текущие элементы матриц L и U определяются текущим элементом матрицы A и предыдущими элементами матриц L и U. Отсюда, т.к. нулевые элементы и единичную диагональ матрицы U запоминать не нужно, в процессе вычислений матрицы L и U могут быть записаны на месте матрицы A, причем L расположена в нижнем треугольнике $(i>=j)$, а U – соответственно в верхнем треугольнике $(i

Примеры приближенных решений систем уравнений онлайн

Задача 1. Решить систему линейных уравнений $Ax=b$ методом Зейделя.
Итерационными методами решение задачи найти с точностью $\varepsilon=10^{-3}$.
УКАЗАНИЕ. Для выполнения достаточного условия сходимости воспользоваться перестановкой строк в исходной системе уравнений.

Решение СЛАУ методом Зейделя

Задача 2. 1) Решите систему линейных уравнений методом «Простой итерации» с точностью 0,001, предварительно оценив число достаточных для этого итераций:
2) Полученное решение используйте для вычисления невязки каждого уравнения.
3) Все полученные приближения решения системы привести в итоговом отчете.
4) Не забываем начинать отчет с формулировки задания.

Решение СЛАУ методом простой итерации

Задача 3. 1) Методом Зейделя решите с точностью 0,001 систему линейных уравнений, приведя ее к виду с диагональным преобладанием, а затем к виду удобному для итераций.
2) Полученное решение используйте для вычисления невязки каждого уравнения.
3) Все полученные приближения решения системы привести в итоговом отчете.
4) Не забываем начинать отчет с формулировки задания.

Решение методом Зейделя, вычисление невязки

Задача 4. Используя метод итераций, решите систему нелинейных уравнений с точностью до 0,001.

Решение системы нелинейных уравнений методом итераций

Задача 5. Используя метод Ньютона, решите систему нелинейных уравнений с точностью до 0,001.

Решение системы нелинейных уравнений методом Ньютона

Задача 6. Решить системы линейных уравнений с точностью до 0.001 методами простой итерации и Гаусса-Зейделя, предварительно проверив на сходимость.

Решение СЛАУ методом простой итерации и Гаусса-Зайделя

Примеры по численным методам

Поиск Лекций

Численные методы решения систем линейных алгебраических уравнений

Численные методы

Конспект лекций для магистров

направления 151000 «Технологические машины и оборудование»

Санкт-Петербург

1. Численные методы линейной алгебры.. 5

1.1. Численные методы решения систем линейных алгебраических уравнений. 5

1.1.1. Метод Гаусса. 5

1.1.2. Метод прогонки. 14

1.1.3. Нормы векторов и матриц. 17

1.1.4. Итерационные методы решения СЛАУ.. 20

Метод простых итераций. 20

Метод Зейделя решения СЛАУ.. 24

1.2. Численные методы решения задач на собственные значения и собственные векторы матриц 26

1.2.1. Основные определения и спектральные свойства матриц. 26

1.2.2. Метод вращений Якоби численного решения задач на собственные значения и собственные векторы матриц. 28

1.2.3. Численная проблема собственных значений и собственных векторов матрицы. Степенной метод. 31

1.2.4. QR – алгоритм нахождения собственных значений матрицы.. 34

2. Решение нелинейных уравнений и систем нелинейных уравнений. 41

2.1. Решение нелинейных уравнений. 41

2.1.1. Метод половинного деления. 42

2.1.2. Метод Ньютона (метод касательных) 42

2.1.3. Метод простой итерации. 43

2.2. Решение систем нелинейных уравнений. 47

2.2.1. Метод Ньютона. 48

2.2.2. Метод простой итерации. 51

3. Теория приближения функций. 55

3.1. Постановка задач приближения функций. 55

3.2. Задача интерполяции. 57

3.2.1. Интерполяционный полином Лагранжа. 58

3.2.2. Интерполяционный полином Ньютона. 59

3.2.3. Погрешность полиномиальной интерполяции. 60

3.2.4. Сплайн — интерполяция. 64

3.2.5. Тригонометрическая интерполяция. 70

3.3. Метод наименьших квадратов. 72

3.4. Численное дифференцирование. 78

3.4.1. Метод Рунге оценки погрешности и уточнения формул численного дифференцирования 80

3.5. Численное интегрирование функций. 83

3.5.1. Формула прямоугольников численного интегрирования. 83

3.5.2. Численное интегрирование с помощью формулы трапеций. 85

3.5.3. Формула Симпсона численного интегрирования. 87

3.5.4. Процедура Рунге оценки погрешности и уточнения формул численного интегрирования 90

4. Численные методы решения обыкновенных дифференциальных уравнений. 94

4.1. Решение задачи Коши. 94

4.1.1. Задача Коши для обыкновенного дифференциального уравнения. 94

4.1.2. Одношаговые методы.. 95

Метод Эйлера (явный) 95

Погрешность метода Эйлера. 96

Модификация метода Эйлера. 96

Неявный метод Эйлера. 96

Метод Эйлера – Коши. 96

Неявный метод Эйлера – Коши. 97

Метод Эйлера – Коши с итерационной обработкой. 97

Первый улучшенный метод Эйлера. 98

Методы Рунге — Кутты.. 98

Метод Рунге – Кутты третьего порядка точности. 99

Метод Рунге – Кутты четвертого порядка точности. 99

Контроль точности на каждом шаге. 100

4.1.3. Решение задачи Коши для системы обыкновенных дифференциальных уравнений 101

Решение задачи Коши для ОДУ второго и более высокого порядка.

4.1.4. Решение дифференциальных уравнений с запаздывающим аргументом.. 112

4.1.5. Многошаговые методы. Метод Адамса. 115

Метод Адамса. 115

Метод Адамса – Бэшфортса — Моултона. 116

Этап предиктор. 116

Этап корректор. 116

4.2. Численные методы решения краевой задачи для ОДУ.. 119

4.2.1. Метод стрельбы.. 120

4.2.2. Конечно – разностный метод решения краевой задачи. 123

5. Численное решение дифференциальных уравнений в частных производных. 126

5.1. Численное решение уравнений параболического типа. Понятие о методе конечных разностей. Основные определения и конечно – разностные схемы. 126

5.1.1. Постановка задач для уравнений параболического типа. 126

5.1.2. Понятие о методе конечных разностей. Применение метода конечных. 127

разностей к решению уравнений параболического типа. 127

5.1.3. Аппроксимация граничных условий, содержащих производные. 132

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

5.2.1 Постановка задач для уравнений гиперболического типа. 137

5.2.2. Конечно – разностная аппроксимация уравнений гиперболического типа. 139

5.3. Метод конечных разностей для решения уравнений эллиптического типа. 143

5.3.1 Постановка задач для уравнений эллиптического типа. 143

5.3.2. Конечно – разностная аппроксимация уравнений эллиптического типа. 144

5.4. Основные понятия, связанные с конечно – разностной аппроксимацией дифференциальных задач 147

Аппроксимация и порядок аппроксимации. 147

Устойчивость. 148

Сходимость и порядок сходимости. 150

6. Основы метода конечных элементов. 151

6.1. Формирование сетки. 151

6.2 Конечно – элементная аппроксимация. 153

6.3. Построение решения. 156

Численные методы линейной алгебры

Численные методы решения систем линейных алгебраических уравнений

Метод Гаусса


Метод прогонки

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

Прямые методы решения СЛАУ:
Метод Крамера
Метод обратной матрицы
Метод Гаусса
Итерационные методы решения линейных алгебраических систем:
Метод простой итерации или метод Якоби
Метод Гаусса – Зейделя

К решению систем линейных алгебраических уравнений сводятся многочисленные практические задачи ( по некоторым оценкам более 75% всех задач). Можно с полным основанием утверждать, что решение линейных систем является одной из самых распространенных и важных задач вычислительной математики.

Конечно, существует много методов и современных пакетов прикладных программ для решения СЛАУ, но для того, чтобы их успешно использовать, необходимо разбираться в основах построения методов и алгоритмов, иметь представления о недостатках и преимуществах используемых методов.

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

Требуется найти решение системы m линейных уравнений, которая записывается в общем виде как

,

Эту систему уравнений можно записать также в матричном виде:

,

где , , .

A – матрица системы, – вектор правых частей, – вектор неизвестных.

При известных A и требуется найти такие , при подстановке которых в систему уравнений она превращается в тождество.

Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A≠0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество.

В дальнейшем будем предполагать наличие единственного решения.

Все методы решения линейных алгебраических задач можно разбить на два класса: прямые (точные) и итерационные (приближенные).

Прямые методы решения СЛАУ

Метод Крамера

При небольшой размерности системы m (m = 2,…,5) на практике часто используют формулы Крамера для решения СЛАУ:

(i = 1, 2, …, m). Эти формулы позволяют находить неизвестные в виде дробей, знаменателем которых является определитель матрицы системы, а числителем – определители матриц Ai, полученных из A заменой столбца коэффициентов при вычисляемом неизвестном столбцом свободных членов. Так А1 получается из матрицы А заменой первого столбца на столбец правых частей f.

Например, для системы двух линейных уравнений

Размерность системы (т.е., число m) является главным фактором, из–за которого формулы Крамера не могут быть использованы для численного решения СЛАУ большого порядка. При непосредственном раскрытии определителей решение системы с m неизвестными требует порядка m!*m арифметических операций. Таким образом, для решения системы, например, из m = 100 уравнений потребуется совершить 10158 вычислительных операций (процесс займёт примерно 1019 лет), что не под силу даже самым мощным современным ЭВМ

Метод обратной матрицы

Если det A ≠ 0, то существует обратная матрица . Тогда решение СЛАУ записывается в виде: . Следовательно, решение СЛАУ свелось к умножению известной обратной матрицы на вектор правых частей. Таким образом, задача решения СЛАУ и задача нахождения обратной матрицы связаны между собой, поэтому часто решение СЛАУ называют задачей обращения матрицы. Проблемы использования этого метода те же, что и при использовании метода Крамера: нахождение обратной матрицы – трудоемкая операция.

Метод Гаусса

Наиболее известным и популярнымпрямым методом решения СЛАУ является метод Гаусса. Этот метод заключается в последовательном исключении неизвестных. Пусть в системе уравнений

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

Если , то, продолжая аналогичное исключение, приходим к системе уравнений с верхней треугольной матрицей

Из нее в обратном порядке находим все значения xi:

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

, j = i+1,i+ 2, …, m;

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

Рассмотрим применение метода Гаусса с выбором главного элемента на примере следующей системы уравнений:

В первом уравнении коэффициент при =0, во втором = 1 и в третьем = -2, т.е. максимальный по модулю коэффициент в третьем уравнении. Поэтому переставим третье и первое уравнение:

Исключим из второго и третьего уравнений с помощью первого. Во втором уравнении исключать не надо. Для исключения из третьего уравнения умножим первое на 0.5 и сложим с третьим:

Рассмотрим второе и третье уравнения. Максимальный по модулю элемент при в третьем. Поэтому поместим его на место второго:

Исключим из третьего уравнения.

Для этого умножим второе на -0.5 и сложим с третьим:

Обратный ход: .

Проверка: 0.5*8+0=4, -3+8-0=5, -2*(-3)+0=6.

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

Часто возникает необходимость в решении СЛАУ, матрицы которые являются слабо заполненными, т.е. содержат много нулевых элементов. В то же время эти матрицы имеют определенную структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами коэффициентов вместо метода Гаусса можно использовать более эффективные методы. Например, метод прогонки, который мы рассмотрим позже при решении краевой задачи для обыкновенного дифференциального уравнения второго порядка.

Итерационные методы решения линейных алгебраических систем

Метод простой итерации или метод Якоби

Напомним, что нам требуется решить систему линейных уравнений, которая в матричном виде записывается как:

,

где , , .

Предположим, что диагональные элементы матриц A исходной системы не равны 0 (aii ≠ 0, i = 1, 2, …, n). Разрешим первое уравнение системы относительно x1, второе относительно x2 и т.д. Получим следующую эквивалентную систему, записанную в скалярном виде:

(1),

Теперь, задав нулевое приближение , по рекуррентным соотношениям (1) можем выполнять итерационный процесс, а именно:

(2)

Аналогично находятся следующие приближения , где в (2) вместо необходимо подставить .

Или в общем случае:

. (3)

или

Условие окончания итерационного процесса .

Достаточное условие сходимости: Если выполнено условие диагонального преобладания, т.е. , то итерационный процесс (3) сходится при любом выборе начального приближения. Если исходная система уравнений не удовлетворяет условию сходимости, то ее приводят к виду с диагональным преобладанием.

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

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

Пример.

Решить систему линейных уравнений с точностью :

=

=

=

–2

Решение прямыми методами, например, обратной матрицей, даёт решение:

Найдем решение методом простой итерации. Проверяем условие диагонального преобладания: , , .

Приводим систему уравнений к виду (1):

Начальное приближение . Дальнейшие вычисления оформим в виде таблицы:

Здесь

,

И т.д., пока не получим, в последнем столбце величину меньшую 0.01, что произойдет на 13 – ой итерации.

Следовательно, приближенное решение имеет вид:

Метод Гаусса – Зейделя

Расчетные формулы имеют вид:

т.е. для подсчета i–й компоненты (k+1)–го приближения к искомому вектору используется уже вычисленное на этом, т.е. (k+1)–м шаге, новые значения первых i–1 компонент.

Подробные формулы имеют вид:

Достаточное условие сходимости этого метода такое же, как и для метода простой итерации, т.е. диагональное преобладание:

Начальное приближение:

Найдем решение предыдущей системы уравнений методом Гаусса – Зейделя.

Расчетные формулы:

Добавить комментарий

Закрыть меню