Банк задач по математике

Задача 7.10.1

Какие из следующих матриц сходящиеся, а какие суммируемые?

\mathbf{A} = \begin{pmatrix} -1/2 & 3/2 & -3/2 \\ 1 & 0 & -1/2 \\ 1 & -1 & 1/2 \end{pmatrix}, \quad \mathbf{B} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, \quad \mathbf{C} = \begin{pmatrix} -1 & -2 & -3/2 \\ 1 & 2 & 1 \\ 1 & 1 & 3/2 \end{pmatrix}.

?

Задача 7.10.2

Для матриц из упражнения 7.10.1 вычислите предел каждой сходящейся матрицы и вычислите предел Чезаро для каждой суммируемой матрицы.

Если $\mathbf{A}$ сходится или суммируема к $\mathbf{G}$ , и если $\mathbf{I}-\mathbf{A} = \mathbf{B}\mathbf{C}$ --- факторизация полного ранга, то $\mathbf{G} = \mathbf{I} - \mathbf{B}(\mathbf{C}\mathbf{B})^{-1}\mathbf{C}$ .

?

Задача 7.10.3

Проверьте, что

\overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) \quad \text{и} \quad \overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) + \sum _{j=0}^{k-1}\mathbf{A}^{k-j-1}\overrightarrow {b}(j) \quad \text{для } k=1,2,3,\ldots

действительно являются соответствующими решениями разностных уравнений $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)$ (однородная система) и $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)+\overrightarrow {b}(k)$ (неоднородная система).

?

Задача 7.10.4

Найдите предельный вектор для следующей игры в напёрстки, вычислив сначала предел Чезаро $\mathbf{G}$ с помощью факторизации полного ранга.

Игра в напёрстки: горошина изначально находится под одним из четырёх напёрстков и после каждого хода перемещается под один из (не более трёх) соседних напёрстков с равной вероятностью, что описывается $4\times 4$ столбцово-стохастической матрицей перехода $\mathbf{A}$ , для которой $\overrightarrow {p}(k) = \mathbf{A}^k\overrightarrow {p}(0)$ задаёт распределение вероятностей по положениям напёрстка после $k$ ходов. Если $\mathbf{I}-\mathbf{A} = \mathbf{B}\mathbf{C}$ — факторизация полного ранга, то предел Чезаро равен $\mathbf{G} = \mathbf{I}-\mathbf{B}(\mathbf{C}\mathbf{B})^{-1}\mathbf{C}$ , а предельный вектор ожидаемых долей равен $\overrightarrow {p} = \mathbf{G}\overrightarrow {p}(0)$ .

?

Задача 7.10.5

Проверьте, что

\overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) \quad \text{и} \quad \overrightarrow {x}(k) = \mathbf{A}^k\overrightarrow {x}(0) + \sum _{j=0}^{k-1}\mathbf{A}^{k-j-1}\overrightarrow {b}(j) \quad \text{при } k=1,2,3,\ldots

действительно являются соответствующими решениями разностных уравнений $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)$ (однородная система) и $\overrightarrow {x}(k+1) = \mathbf{A}\overrightarrow {x}(k)+\overrightarrow {b}(k)$ (неоднородная система).

?

Задача 7.10.6

Докажите, что если существует матричная норма, для которой $\left\| \mathbf{A}\right\| < 1$ , то $\lim_{k\to \infty }\mathbf{A}^k = \mathbf{0}$ .

?

Задача 7.10.7

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

\mathbf{A}_1 = \begin{pmatrix} 1 & 2 & -2 \\ 1 & 1 & 1 \\ 2 & 2 & 1 \end{pmatrix}, \quad \mathbf{A}_2 = \begin{pmatrix} 2 & -1 & 1 \\ 2 & 2 & 2 \\ -1 & -1 & 2 \end{pmatrix}.

?

Задача 7.10.8

(a)(b)(c)(d)

Пусть $\mathbf{A} = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}$ (матрица конечных разностей из примера 1.4.1).

?

(a)

Проверьте, что $\mathbf{A}$ удовлетворяет специальным условиям, гарантирующим справедливость формулы оптимальной релаксации SOR: $\operatorname {det}\left(\alpha \mathbf{D}-\mathbf{L}-\mathbf{U}\right) = \operatorname {det}\left(\alpha \mathbf{D}-\beta \mathbf{L}-\beta^{-1}\mathbf{U}\right)$ для всех вещественных $\alpha$ и $\beta \ne 0$ , а итерационная матрица Якоби $\mathbf{H}_J$ имеет вещественные собственные значения, причём $\rho (\mathbf{H}_J)<1$ , где $\mathbf{D}$ , $\mathbf{L}$ , $\mathbf{U}$ — диагональная, строго нижнетреугольная и строго верхнетреугольная части матрицы $\mathbf{A}$ .

(b)

Определите оптимальный параметр релаксации SOR, если известно, что $\omega_{\text{opt}} = \dfrac {2}{1+\sqrt{1-\rho^2(\mathbf{H}_J)}}$ и $\rho (\mathbf{H}_{\omega_{\text{opt}}}) = \omega_{\text{opt}}-1$ .

(c)

Найдите асимптотические скорости сходимости для методов Якоби, Гаусса--Зейделя и оптимального SOR.

(d)

Используя $\overrightarrow {x}(0) = (1,1,1)^T$ и $\overrightarrow {b} = (2,4,6)^T$ , выполните несколько шагов методов Якоби, Гаусса--Зейделя и оптимального SOR для решения системы $\mathbf{A}\overrightarrow {x}=\overrightarrow {b}$ , пока не станет виден характер сходимости.

Задача 7.10.9

Докажите, что если $\rho (\mathbf{H}_{\omega }) < 1$ , где $\mathbf{H}_{\omega }$ — итерационная матрица метода SOR, то $0 < \omega < 2$ .

?

Примечание.

?

Указание: используйте $\operatorname {det}\left(\mathbf{H}_{\omega }\right)$ , чтобы показать, что $\left|\lambda_k\right| \ge \left|1-\omega \right|$ для некоторого $\lambda_k \in \sigma (\mathbf{H}_{\omega })$ .

Задача 7.10.10

Покажите, что спектральный радиус итерационной матрицы Якоби для дискретного лапласиана $\mathbf{L}_{n^2\times n^2}$ , описанного в примере 7.6.2, равен $\rho (\mathbf{H}_J) = \cos \bigl(\pi /(n+1)\bigr)$ .

?

Задача 7.10.11

Рассмотрим скалярную последовательность $\left\{ \alpha_1, \alpha_2, \alpha_3, \ldots \right\}$ и связанную с ней последовательность средних Чезаро $\left\{ \mu_1, \mu_2, \mu_3, \ldots \right\}$ , где $\mu_n = (\alpha_1+\alpha_2+\cdots +\alpha_n)/n$ . Докажите, что если $\left\{ \alpha_n\right\}$ сходится к $\alpha$ , то $\left\{ \mu_n\right\}$ также сходится к $\alpha$ .

?

Примечание.

?

Как и для скаляров, векторная последовательность $\left\{ \overrightarrow {v}_n\right\}$ в конечномерном пространстве сходится к $\overrightarrow {v}$ тогда и только тогда, когда для каждого $\varepsilon >0$ найдётся натуральное число $N=N(\varepsilon )$ , такое что $\left\| \overrightarrow {v}_n-\overrightarrow {v}\right\| <\varepsilon$ для всех $n\ge N$ , причём неважно, какая норма используется. Поэтому ваше доказательство должно быть справедливо и для векторов (и матриц).

Задача 7.10.12

Для матриц с неположительными внедиагональными элементами ( $Z$ -матриц) докажите, что следующие утверждения эквивалентны.

?

(a)

$\mathbf{A}$ является $M$ -матрицей.

(b)

Все ведущие главные миноры $\mathbf{A}$ положительны.

(c)

$\mathbf{A}$ имеет $\mathbf{L}\mathbf{U}$ -разложение, причём и $\mathbf{L}$ , и $\mathbf{U}$ являются $M$ -матрицами.

(d)

Существует вектор $\overrightarrow {x}>\overrightarrow {0}$ такой, что $\mathbf{A}\overrightarrow {x}>\overrightarrow {0}$ .

(e)

Каждый $a_{ii}>0$ и $\mathbf{A}\mathbf{D}$ диагонально доминантна для некоторой диагональной матрицы $\mathbf{D}$ с положительными диагональными элементами.

(f)

$\mathbf{A}\overrightarrow {x} \ge \overrightarrow {0}$ влечёт $\overrightarrow {x} \ge \overrightarrow {0}$ .

Задача 7.10.13

(a)(b)

Предположим, что $\lambda \in \sigma (\mathbf{A})$ , и пусть $\mathbf{M}_1 = \mathbf{A}-\lambda \mathbf{I}$ . Следующая процедура даёт значение $\operatorname {index}(\lambda )$ : разложим $\mathbf{M}_1 = \mathbf{B}_1\mathbf{C}_1$ как факторизацию полного ранга, положим $\mathbf{M}_2 = \mathbf{C}_1\mathbf{B}_1$ , разложим $\mathbf{M}_2 = \mathbf{B}_2\mathbf{C}_2$ как факторизацию полного ранга, положим $\mathbf{M}_3 = \mathbf{C}_2\mathbf{B}_2$ , и так далее. В общем случае $\mathbf{M}_i = \mathbf{C}_{i-1}\mathbf{B}_{i-1}$ , где $\mathbf{M}_{i-1} = \mathbf{B}_{i-1}\mathbf{C}_{i-1}$ --- факторизация полного ранга.

?

(a)

Объясните, почему эта процедура должна в конечном счёте дать матрицу $\mathbf{M}_k$ , которая либо невырождена, либо нулевая.

(b)

Докажите, что если $k$ --- наименьшее натуральное число такое, что $\mathbf{M}_k^{-1}$ существует или $\mathbf{M}_k = \mathbf{0}$ , то

\operatorname {index}(\lambda ) = \begin{cases} k-1 & \text{если } \mathbf{M}_k \text{ невырождена}, \\ k & \text{если } \mathbf{M}_k = \mathbf{0}. \end{cases}

Задача 7.10.14

Используя процедуру из задачи 7.10.13, найдите индекс каждого собственного значения $\mathbf{A} = \begin{pmatrix} -3 & -8 & -9 \\ 5 & 11 & 9 \\ -1 & -2 & 1 \end{pmatrix}$ .

?

Примечание.

?

Подсказка: $\sigma (\mathbf{A}) = \left\{ 4,1\right\}$ .

Задача 7.10.15

(a)(b)

Пусть $\mathbf{A}$ --- матрица, заданная в задаче 7.10.14.

?

(a)

Найдите жорданову форму для $\mathbf{A}$ .

(b)

Для произвольной функции $f$ , определённой на $\mathbf{A}$ , найдите интерполяционный полином Эрмита и опишите $f(\mathbf{A})$ .

Задача 7.10.16

Пусть дана матрица $\mathbf{B}_{n\times n}$ ранга $r$ такая, что $\operatorname {index}(\mathbf{B}) \le 1$ (т.е. $\operatorname {index}(\lambda =0)\le 1$ ), жорданова форма для $\mathbf{B}$ имеет вид $\begin{pmatrix} 0 & 0 \\ 0 & \mathbf{C}_{r\times r} \end{pmatrix} = \mathbf{P}^{-1}\mathbf{B}\mathbf{P}$ , так что $\mathbf{B} = \mathbf{P}\begin{pmatrix} 0 & 0 \\ 0 & \mathbf{C} \end{pmatrix}\mathbf{P}^{-1}$ , где $\mathbf{C}$ невырождена. Это означает, что $\mathbf{B}$ принадлежит алгебраической группе $\mathcal{G}$ относительно умножения матриц, и обратный к $\mathbf{B}$ элемент в $\mathcal{G}$ есть $\mathbf{B}^{\# } = \mathbf{P}\begin{pmatrix} 0 & 0 \\ 0 & \mathbf{C}^{-1} \end{pmatrix}\mathbf{P}^{-1}$ ; $\mathbf{B}^{\# }$ называется групповым обратным для $\mathbf{B}$ . Докажите, что если $\lim_{k\to \infty }\mathbf{A}^k$ существует и $\mathbf{B} = \mathbf{I}-\mathbf{A}$ , то

\lim _{k\to \infty }\mathbf{A}^k = \mathbf{I}-\mathbf{B}\mathbf{B}^{\# }.

Иными словами, предельную матрицу можно охарактеризовать как разность двух единичных элементов --- $\mathbf{I}$ является единицей в мультипликативной группе невырожденных матриц, а $\mathbf{B}\mathbf{B}^{\# }$ является единичным элементом в мультипликативной группе, содержащей $\mathbf{B}$ .

Пределы степеней: для $\mathbf{A} \in \mathbb {C}^{n \times n}$ , $\lim_{k\to \infty }\mathbf{A}^k$ существует тогда и только тогда, когда $\rho (\mathbf{A})<1$ , либо $\rho (\mathbf{A})=1$ , причём $\lambda =1$ --- единственное собственное значение на единичной окружности, и $\lambda =1$ полупростое.

?

Задача 7.10.17

Если $\mathbf{M}_{n\times n}$ — групповая матрица (т.е. если $\operatorname {index}(\mathbf{M}) \le 1$ ), то групповую обратную матрицу $\mathbf{M}$ можно охарактеризовать как единственное решение $\mathbf{M}^{\# }$ уравнений $\mathbf{M}\mathbf{M}^{\# }\mathbf{M} = \mathbf{M}$ , $\mathbf{M}^{\# }\mathbf{M}\mathbf{M}^{\# } = \mathbf{M}^{\# }$ и $\mathbf{M}\mathbf{M}^{\# } = \mathbf{M}^{\# }\mathbf{M}$ . Более того, некоторые авторы используют именно эти уравнения для определения $\mathbf{M}^{\# }$ . Используя эту характеризацию, покажите, что если $\mathbf{M} = \mathbf{B}\mathbf{C}$ — произвольное разложение $\mathbf{M}$ на множители полного ранга, то $\mathbf{M}^{\# } = \mathbf{B}(\mathbf{C}\mathbf{B})^{-2}\mathbf{C}$ . В частности, если $\mathbf{M} = \mathbf{U}_1\mathbf{D}\mathbf{V}_1^{*}$ — разложение полного ранга, полученное из сингулярного разложения, то

\mathbf{M}^{\# } = \mathbf{U}_1\mathbf{D}^{-1/2}(\mathbf{V}_1^{*}\mathbf{U}_1)^{-2}\mathbf{D}^{-1/2}\mathbf{V}_1^{*} = \mathbf{U}_1\mathbf{D}^{-1}(\mathbf{V}_1^{*}\mathbf{U}_1)^{-2}\mathbf{V}_1^{*} = \mathbf{U}_1(\mathbf{V}_1^{*}\mathbf{U}_1)^{-2}\mathbf{D}^{-1}\mathbf{V}_1^{*}.

?

Разностные уравнения, пределы и суммируемость