1.6

Плохо обусловленные системы

[7/71%]
Показать
LaTeX
Задача 1.6.1

Рассмотрим плохо обусловленную систему из примера 1.6.1:

.835x+.667y=.168,.333x+.266y=.067. \begin{aligned} .835 x + .667 y & = .168, \\ .333 x + .266 y & = .067. \end{aligned}
?
(a)

Опишите результат, который получится при попытке решить систему с использованием 5-значной арифметики без масштабирования.

(b)

Снова используя 5-значную арифметику, сначала выполните построчное масштабирование системы, прежде чем пытаться её решить. Опишите, насколько это помогает.

(c)

Теперь используйте 6-значную арифметику без масштабирования. Сравните результаты с точным решением.

(d)

Используя 6-значную арифметику, вычислите невязки для вашего решения из пункта (в) и проинтерпретируйте результаты.

(e)

Для того же решения, полученного в пункте (в), снова вычислите невязки, но на этот раз используя 7-значную арифметику, и проинтерпретируйте результаты.

(f)

Сформулируйте заключительное утверждение, обобщающее выводы пунктов (а)--(д).

Задача 1.6.2

Возмутите плохо обусловленную систему из упражнения 1.6.1 выше так, чтобы получить следующую систему:

.835x+.667y=.1669995,.333x+.266y=.066601. \begin{aligned} .835 x + .667 y & = .1669995, \\ .333 x + .266 y & = .066601. \end{aligned}
?
(a)

Определите точное решение и сравните его с точным решением системы из упражнения 1.6.1.

(b)

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

Задача 1.6.3

Рассмотрим две прямые линии, определяемые графиками следующих двух уравнений:

.835x+.667y=.168,.333x+.266y=.067. \begin{aligned} .835 x + .667 y & = .168, \\ .333 x + .266 y & = .067. \end{aligned}
?
(a)

Используя 5-значную арифметику, вычислите наклоны каждой из линий, а затем используя 6-значную арифметику, сделайте то же самое. В каждом случае изобразите графики на координатной системе.

(b)

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

(c)

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

Задача 1.6.4

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

?
(a)
1.001x−y=.235,x+.0001y=.765. \begin{aligned} 1.001 x - y & = .235, \\ x + .0001 y & = .765. \end{aligned}
(b)
1.001x−y=.235,x+.9999y=.765. \begin{aligned} 1.001 x - y & = .235, \\ x + .9999 y & = .765. \end{aligned}
(c)
1.001x+y=.235,x+.9999y=.765. \begin{aligned} 1.001 x + y & = .235, \\ x + .9999 y & = .765. \end{aligned}
Задача 1.6.5

Определите точное решение следующей системы:

8x+5y+2z=15,21x+19y+16z=56,39x+48y+53z=140. \begin{aligned} 8 x + 5 y + 2 z & = 15, \\ 21 x + 19 y + 16 z & = 56, \\ 39 x + 48 y + 53 z & = 140. \end{aligned}

Теперь замените 1515 на 1414 в первом уравнении и снова решите систему с использованием точной арифметики. Является ли система плохо обусловленной?

?
Задача 1.6.6

Покажите, что система

v−w−x−y−z=0,w−x−y−z=0,x−y−z=0,y−z=0,z=1, \begin{aligned} v - w - x - y - z & = 0, \\ w - x - y - z & = 0, \\ x - y - z & = 0, \\ y - z & = 0, \\ z & = 1, \end{aligned}

плохо обусловлена, рассмотрев следующую возмущённую систему:

v−w−x−y−z=0,−115v+w−x−y−z=0,−115v+x−y−z=0,−115v+y−z=0,−115v+z=1. \begin{aligned} v - w - x - y - z & = 0, \\ -\frac{1}{15} v + w - x - y - z & = 0, \\ -\frac{1}{15} v + x - y - z & = 0, \\ -\frac{1}{15} v + y - z & = 0, \\ -\frac{1}{15} v + z & = 1. \end{aligned}
?
Задача 1.6.7

Пусть f(x)=sin⁡πxf(x) = \sin \pi x на [0,1][0, 1]. Цель этой задачи — определить коэффициенты αi\alpha_{i} кубического многочлена

p(x)=∑i=03αixi p(x) = \sum _{i=0}^{3} \alpha _{i} x^{i}

который максимально близок к f(x)f(x) в том смысле, что

r=∫01[f(x)−p(x)]2 dx=∫01[f(x)]2 dx−2∑i=03αi∫01xif(x) dx+∫01(∑i=03αixi)2dx \begin{aligned} r & = \int _{0}^{1} [f(x) - p(x)]^{2} \, dx \\ & = \int _{0}^{1} [f(x)]^{2} \, dx - 2 \sum _{i=0}^{3} \alpha _{i} \int _{0}^{1} x^{i} f(x) \, dx + \int _{0}^{1} \left( \sum _{i=0}^{3} \alpha _{i} x^{i} \right)^{2} dx \end{aligned}

минимально по величине.

?
(a)

Чтобы минимизировать rr, наложите условие ∂r/∂αi=0\partial r / \partial \alpha_{i} = 0 для каждого i=0,1,2,3i = 0, 1, 2, 3, и покажите, что это приводит к системе линейных уравнений, расширенная матрица которой равна [H4∣b][H_{4} \mid b], где H4H_{4} и bb заданы как

H4=[1121314]2mm]1213141513141516]2mm]14151617]иb=[2π1π]2mm]1π−4π31π−6π3]. H_{4} = \begin{bmatrix} 1 & \dfrac {1}{2} & \dfrac {1}{3} & \dfrac {1}{4} \\ ]2mm] \dfrac {1}{2} & \dfrac {1}{3} & \dfrac {1}{4} & \dfrac {1}{5} \\[2mm] \dfrac {1}{3} & \dfrac {1}{4} & \dfrac {1}{5} & \dfrac {1}{6} \\ ]2mm] \dfrac {1}{4} & \dfrac {1}{5} & \dfrac {1}{6} & \dfrac {1}{7} \end{bmatrix} \quad \text{и} \quad b = \begin{bmatrix} \dfrac {2}{\pi } \\[2mm] \dfrac {1}{\pi } \\ ]2mm] \dfrac {1}{\pi } - \dfrac {4}{\pi ^{3}} \\[2mm] \dfrac {1}{\pi } - \dfrac {6}{\pi ^{3}} \end{bmatrix}.

Любая матрица HnH_{n}, имеющая тот же вид, что и H4H_{4}, называется матрицей Гильберта порядка nn.

(b)

Системы с матрицами Гильберта сильно плохо обусловлены, и плохая обусловленность усугубляется с ростом размера. Используя точную арифметику и метод гауссова исключения, приведите H4H_{4} к треугольному виду. Предполагая, что случай n=4n = 4 типичен, объясните, почему общая система [Hn∣b][H_{n} \mid b] будет плохо обусловлена. Заметьте, что даже полный выбор ведущего элемента здесь не помогает.