Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


Основные положения численного анализа


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


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


В численном анализе используются два класса численных методов:


1. Прямые методы, позволяющие найти решение за определенное число операций.


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


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


Один из типов погрешностей обусловлен неадекватностью выбранной математической модели исходной физической. Эта неадекватность в большей или меньшей степени присуща всем приближенно решаемым задачам. Данная погрешность является неустранимой. Неточность (неопределенность) задания исходных данных приводит также к неустранимым погрешностям.


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


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


Пусть [math]x[/math] — точное, но, как правило, неизвестное значение некоторой величины, а [math]\widehat{x}[/math] — ее известное приближенное значение.


Абсолютной погрешностью приближения [math]\widehat{x}[/math] называется разность [math]\Delta=\bigl|x-\widehat{x}\bigr|[/math] (в общем случае [math]\Delta\widehat{x}[/math] имеет размерность величины [math]x[/math]).


Относительная погрешность приближения [math]\widehat{x}[/math] обозначается [math]\delta[/math] и выражается отношением [math]\delta= \frac{\Delta\widehat{x}}{|\widehat{x}|}[/math] ([math]\delta[/math] — безразмерная величина, [math]\widehat{x}\ne0[/math]). Часто величина [math]\delta[/math] вычисляется в процентах, и тогда она умножается на сто.


Так как величина [math]x[/math], как правило, неизвестна, а погрешность необходимо определять, то в рассмотрение вводится предельная абсолютная погрешность [math]\Delta(\widehat{x}):[/math]


[math]\Delta\widehat{x}= |x-\widehat{x}|\leqslant \Delta(\widehat{x}).[/math]

Раскрывая в этом неравенстве модуль, получаем соотношение, задающее отрезок, которому принадлежит точное значение: [math]\widehat{x}-\Delta(\widehat{x}) \leqslant x\leqslant \Delta(\widehat{x})[/math]. Таким образом, величина [math]x[/math] находится в ∆-окрестности (дельта-окрестности), определяемой величинами [math]\widehat{x}[/math] и [math]\Delta(\widehat{x})[/math].


Предельная относительная погрешность приближения [math]\widehat{x}[/math] определяется отношением [math]\delta(\widehat{x})= \frac{\Delta(\widehat{x})}{|\widehat{x}|}[/math].


Такие погрешности оцениваются при рассмотрении численных методов. Эти оценки могут производиться до выполнения вычислений (априорные оценки) и после них (апостериорные оценки).


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




Норма матриц: понятие, определение, примеры


При решении многих практических задач необходимо как-то "измерять" матрицы, чтобы говорить, что одна матрица больше другой. Правило, по которому матрице (в частности, матрице-столбцу) ставится в соответствие некоторое неотрицательное число, имеющее смысл меры, определяет понятие норма матрицы.


Нормой матрицы-столбца [math]x=\begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}[/math] называется функция [math]\|x\|[/math], удовлетворяющая следующим аксиомам:


1. [math]\|x\|\geqslant0[/math] для любого столбца [math]x[/math], причем [math]\|x\|=0[/math] в том и только в том случае, если [math]x[/math] — нулевой столбец;

2. [math]\|\alpha x\|=|\alpha|\cdot\|x\|[/math] для любого действительного числа [math]\alpha[/math];

3. [math]\|x+y\|\leqslant\|x\|+\|y\|[/math] для любых двух столбцов [math]x[/math] и [math]y[/math] размеров [math](n\times1)[/math].


Аксиома 3 называется неравенством треугольника.


Примером нормы матрицы-столбца может быть семейство норм


[math]\|x\|= \Biggl(\sum_{i=1}^{n}|x_i|^p\Biggr)^{1/p},[/math]

где при любом целом положительном [math]p[/math] определяется функция, удовлетворяющая условиям 1-3.

Приведем часто используемые нормы матриц-столбцов.


1. [math]\|x\|_1=\max_{i\in\mathbb{N}}|x_i|[/math] — максимум среди модулей элементов столбца;


2. [math]\textstyle{\|x\|_2=\sum\limits_{i=1}^{n}|x_i|}[/math] — сумма модулей элементов столбца;


3. [math]\textstyle{\|x\|_3=\sqrt{\sum\limits_{i=1}^{n}x_i^2}}[/math] — квадратный корень из суммы квадратов элементов.


Последняя норма называется евклидовой, так как совпадает с модулем столбца (длиной вектора), т.е. [math]\|x\|_3=|x|=\sqrt{x^Tx}[/math].




Замечания 10.1


1. Можно показать, что справедливы следующие соотношения


[math]\|x\|_2\geqslant\|x\|_3\geqslant\|x\|_1[/math], а также [math]\sqrt{n}\cdot\|x\|_3\geqslant\|x\|_2,~ \sqrt{n}\cdot\|x\|_1\geqslant\|x\|_3[/math].

2. Норма может быть использована при анализе сходимости последовательностей матриц-столбцов.


Последовательность матриц-столбцов [math]\bigl\{x^{(1)},x^{(2)},\ldots,x^{(k)},\ldots\bigr\}[/math] сходится к столбцу [math]x_{\ast}[/math], если [math]\lim_{k\to+\infty}x_i^{(k)}=x_{\ast i}[/math], для всех [math]i=1,2,\ldots,n[/math]. Для того чтобы последовательность [math]\bigl\{x^{(1)},x^{(2)}, \ldots,x^{(k)},\ldots\bigr\}[/math] сходилась к столбцу х., необходимо и достаточно, чтобы [math]\lim_{k\to+\infty}\bigl\|x^{(k)}-x_{\ast}\bigr\|=0[/math].


3. Для определения псевдорешений систем линейных алгебраических уравнений ранее использовалась евклидова норма [math]\|x\|_3[/math].


4. Нормы позволяют оценить скорость сходимости последовательностей. Рассмотрим последовательность [math]\bigl\{x^{(k)}\bigr\}[/math], сходящуюся к [math]x_{\ast}[/math]. Предположим, что все ее элементы различны и ни один из них не совпадает с [math]x_{\ast}[/math]. Наиболее эффективный способ оценивания скорости сходимости состоит в сопоставлении расстояния [math]\bigl\|x^{(k+1)}-x_{\ast}\bigr\|[/math] между [math]x^{(k+1)}[/math] и [math]x_{\ast}[/math] с расстоянием [math]\bigl\|x^{(k)}-x_{\ast}\bigr\|[/math] между [math]x^{(k)}[/math] и [math]x_{\ast}[/math].


Последовательность [math]\bigl\{x^{(k)}\bigr\}[/math] называется сходящейся с порядком [math]{p}[/math], если [math]{p}[/math] — максимальное число, для которого


[math]0\leqslant \lim_{k\to+\infty} \frac{\|x^{(k+1)}-x_{\ast}\|}{\|x^{(k)}-x_{\ast}\|^p} < +\infty.[/math]

Поскольку величина [math]{p}[/math] определяется предельными свойствами [math]\bigl\{x^{(k)}\bigr\}[/math], она называется асимптотической скоростью сходимости.


Если последовательность [math]\bigl\{x^{(k)}\bigr\}[/math] — сходящаяся с порядком [math]{p}[/math], то число


[math]c=\lim_{k\to+\infty} \frac{\|x^{(k+1)}-x_{\ast}\|}{\|x^{(k)}-x_{\ast}\|^p}\,.[/math]

называется асимптотическим параметром ошибки. Если [math]p=1,~ c<1[/math], то сходимость линейная, если [math]p=2[/math] — квадратичная, если [math]p=3[/math] — кубическая и т.д. Если [math]p>1[/math] или [math]p=1,~c=0[/math], то сходимость сверхлинейная. Линейная сходимость является синонимом сходимости со скоростью геометрической профессии. Сверхлинейная сходимость является более быстрой, чем определяемая любой геометрической прогрессией.


Пример 10.1. Вычислить нормы матрицы-столбца [math]x=\begin{pmatrix} 1&-2&3&-4 \end{pmatrix}^T[/math].


Решение.


[math]\begin{aligned} \mathcf{1)}~\, \|x\|_1&= \max_{i\in\mathbb{N}}|x_i|= \max\bigl\{|1|,|-2|,|3|,|-4|\bigr\}=4\,;\\[5pt] \mathsf{2)}~\, \|x\|_2&= \sum_{i=1}^{4}|x_i|= |1|+|-2|+|3|+|-4|=10\,;\\[5pt] \mathsf{3)}~\, \|x\|_3&= \sqrt{\sum_{i=1}^{4}x_i^2}= \sqrt{1^2+(-2)^2+3^2+(-4)^2}=\sqrt{30}\,. \end{aligned}[/math]


Заметим, что свойство [math]\|x\|_2\geqslant\|x\|_3\geqslant\|x\|_1[/math], очевидно, выполняется.




Пусть [math]A[/math] — произвольная матрица размеров [math](m\times n)[/math].


Нормой матрицы [math]A[/math] называется функция [math]\|A\|[/math], удовлетворяющая следующим аксиомам:


1) [math]\|A\|\geqslant0[/math] для любой матрицы [math]A[/math], причем [math]\|A\|=0[/math] в том и только в том случае, если [math]A[/math] — нулевая матрица;


2) [math]\|\alpha\cdot A\|=|\alpha|\cdot\|A\|[/math] для любого действительного числа [math]\alpha[/math];


3) [math]\|A+B\|\leqslant\|A\|+\|B\|[/math] для любых двух матриц [math]A[/math] и [math]B[/math] размеров [math](m\times n)[/math] (неравенство треугольника);


4) [math]\|A\cdot B\|\leqslant\|A\|\cdot\|B\|[/math] для любых двух матриц, у которых определено произведение.


Матричные нормы удобно определять через нормы матриц-столбцов. Для этого, задавшись какой-нибудь нормой для матриц-столбцов, рассматриваются значения [math]\|Ax\|[/math] при всевозможных х, удовлетворяющих условию [math]\|x\|=1[/math]. Максимальное из этих значений, которое найдется всегда, берется в качестве нормы матрицы [math]A\colon\, \|A\|= \max_{\|x\|=1}\|Ax\|[/math]. Такую матричную норму называют индуцированной.


Заметим, что в качестве определения индуцированной матричной нормы часто используется выражение [math]\|A\|=\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}[/math], характеризующее максимальную величину, на которую преобразование, описываемое матрицей [math]A[/math], может растянуть любой ненулевой вектор в заданной норме.


Наиболее употребительными являются следующие формулы для вычисления значений норм матриц с действительными элементами.


1) [math]\textstyle{\|A\|_1= \max\limits_{i\in\mathbb{N}}\sum\limits_{j=1}^{n}|a_{ij}|}[/math] — максимум суммы модулей элементов в строке;


2) [math]\textstyle{\|A\|_2= \max\limits_{j\in\mathbb{N}}\sum\limits_{i=1}^{n}|a_{ij}|}[/math] максимум суммы модулей элементов в столбце;


3) [math]\|A\|_3=\sqrt{\max_{i\in\mathbb{N}}\lambda_i(A^TA)}[/math] — квадратный корень из максимального собственного значения [math]\lambda_i[/math] матрицы [math]A^TA[/math];


4) [math]\textstyle{\|A\|_4= \sqrt{\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} a_{ij}^2}}[/math] — квадратный корень из суммы квадратов элементов.


Заметим, что вычисление нормы [math]\|A\|_3= \sqrt{\max_{i\in\mathbb{N}} \lambda_i(A^TA)}[/math] связано с весьма трудоемкими операциями. Поскольку справедливо неравенство


[math]\|A\|_3=\sqrt{\max_{i\in\mathbb{N}} \lambda_i(A^TA)} \leqslant \|A\|_4= \sqrt{\sum\limits_{i=1}^{n} \sum_{j=1}^{n} a_{ij}^2}\,[/math]

то норма [math]\|A\|_4[/math] часто используется в оценках вместо [math]\|A\|_3[/math]. Норма [math]\|A\|_4[/math] возникает, если матрице [math]A[/math] поставить в соответствие "длинный столбец":


[math]\begin{pmatrix}a_{11},a_{21},\ldots, a_{m1},a_{12},a_{22},\ldots, a_{m2},\ldots,a_{nn} \end{pmatrix}^T[/math] и применить норму [math]\|x\|_3[/math].



Пример 10.2. Вычислить нормы матриц [math]A=\begin{pmatrix}1&-2&3\\ 4&5&-6\\ -7&8&9 \end{pmatrix}\!,~ B=\begin{pmatrix}1&0&0\\ 0&1&0\\ 0&0&1 \end{pmatrix}[/math].


Решение. а)


[math]\begin{aligned}\|A\|_1&= \max\bigl\{|1|+|-2|+|3|;\, |4|+|5|+|-6|;\, |-7|+|8|+|9|\bigr\}= \max\{6;\,15;\,24\}=24;\\[5pt] \|A\|_2&= \max\bigl\{|1|+|4|+|-7|;\, |-2|+|5|+|8|;\, |3|+|-6|+|9|\bigr\}= \max\{12;15;18\}=18;\\[5pt] \|A\|_4&= \sqrt{1^2+(-2)^2+3^2+4^2+5^2+(-6)^2+(-7)^2+8^2+9^2}=\\[2pt] &=\sqrt{1+4+9+16+25+36+49+64+81}= \sqrt{285};\end{aligned}[/math]

б) [math]\|B\|_1=\|B\|_2=1,\,~ \|B\|_4=\sqrt{1+1+1}=\sqrt{3}[/math].




Норма матриц может быть использована при анализе сходимости различных численных процедур. Пусть имеется последовательность матриц [math]\bigl\{A^{(1)},\ldots,A^{(k)},\ldots\bigr\}[/math] размеров [math]m\times n[/math]. Матрица [math]A[/math] называется пределом последовательности матриц [math]\bigl\{A^{(1)},\ldots,A^{(k)},\ldots\bigr\}[/math], если [math]\lim_{k\to+\infty}a_{ij}^{(k)}=a_{ij}[/math] для всех [math]i=1,\ldots,m[/math] и [math]j=1,\ldots,n[/math]. Это обозначается [math]\lim_{k\to+\infty}A^{(k)}=A[/math].


Для сходимости последовательности матриц [math]\bigl\{A^{(1)},\ldots,A^{(k)},\ldots\bigr\}[/math] к матрице [math]A[/math] необходимо и достаточно, чтобы [math]\lim_{k\to+\infty}\bigl\|A^{(k)}-A\bigr\|=0[/math]. При этом последовательность, составленная из норм матриц [math]A^{(k)}[/math], сходится к норме матрицы [math]A[/math], т.е. [math]\lim_{k\to+\infty} \bigl\|A^{(k)}\bigr\|=\|A\|[/math].


Отметим некоторые свойства предела матриц. Если [math]\lim_{k\to +\infty}A^{(k)}=A,~ \lim_{k\to+\infty}B^{(k)}=B[/math], то:


[math]\begin{array}{ll}\mathsf{1)}~ \lim\limits_{k\to+\infty}\bigl[A^{(k)}\pm B^{(k)}\bigr]=A\pm B;&\qquad \mathsf{2)}~ \lim\limits_{k\to+\infty}\bigl[A^{(k)}\cdot B^{(k)}\bigr]=A\cdot B;\\\\[-5pt] \mathsf{3)}~ \lim\limits_{k\to+\infty}\bigl[A^{(k)}\bigr]^{-1}=A^{-1};&\qquad \mathsf{4)}~ \lim\limits_{k\to+\infty}\bigl[CA^{(k)}\bigr]=CA,~ \lim\limits_{k\to+\infty}\bigl[A^{(k)}D\bigr]=AD.\end{array}[/math]

где считается, что все операции определены.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved