Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
IеLP- 0
) т 1 } т2
(20.19)
~ ' ii< л, -*. >
где С, - нижняя треугольная невырожденная тх X щ^^щрщщ^ f
Найдем т, -вектор у, из нижней треугольной еИемЩ! ,
С1У1 = d. ., (20.20) Вычислим вектор Он
f = f-Eiyl. (20.21) Решим задачу наименьших квадратов
ЕгУг^Т (20.22)
относительно п — тх-вектора у2. Наконец,вычислим рааяал исходной
задачи . ^,'-)',
(20.23)
Уг1
Шаги реального вычислительного процесса описываются нижеследующим алгоритмом. Поначалу матрицы и векторы C,d,E и / хранятся в массивах с теми же именами. Массив g имеет длину тх. Каждый из массивов h, и и р имеет длину п - тх. Решение минимальной длины будет помещено в массив х длины п. Параметр г — это задаваемый пользователем допуск, нужный на шаге 6.
Алгоритм 20.24. LSE(C, d, Е, f, m,. т2. п, g, h, и, р, х, т).
1. Для i := 1, m , выполнить алгоритм Н1(/, i + 1, и. cilt gl, ci + i,i. m i-О (см. (20.19)). Здесь и на шаге 2 алгоритмы HI и Н2 оперируют со строками массивов С и Е.
2. Для / := 1,ги, выполнить алгоритм Н2(/, / + 1, п, Сц, gi, ex i, m2) (см. (20.19)). Если матрицы Си? хранятся единым (rrti + m2) X n-мас-
сивом (назовем его W), то шаги 1 и 2 можно объединить: для / : = 1.....m,
выполнить алгоритм HI(/', /' +1,и, нп, git + m\+m2 — i).
vm
3. Положить *i : = </1 /с 11. Если т, = 1, перейти к шагу 5.
4. Для / := 2.....т, положить (см. (20.20))
5. Для / :- 1, ...,т2 положит» (см. (20.21))
1 etjx
i = 1
6. Выполнить в соответствии с (14.9) алгоритм HFTI(e 1>m ( + i, тг, п- mi, f, т, Jtmi + i, к, п, и, р). (Решение уг задачи (20.22) теперь вычислено и помешено в ячейки xt, / : = m, + 1,п.)
7. Для /':= Wi, те, - 1..... 1 выполнить алгоритм Н2(/, / + 1, п, сП,
gi, х, 1) (см. (20.23)). Отметим, что в списке параметров алгоритма Н2 содержится ссылка на строки массива С, а преобразования применяются к одномерному массиву х.
8. Комментарий. В массиве с именем х теперь находится решение минимальной длины задачи НКУ.
В качестве примера задачи НКУ рассмотрим минимизацию \\b'x-f\\ при условии Сх = J, где
[ 0,4087
0,4302 0,6246
d = 0,1376,
0.1593 ],
0,3516 I 0,3384 J '
I 0,6593 1 10,9666 J
(20.25)
(20.26) (20.27)
(20.28)
Ортогональная матрица Хаусхолдера, которая приводят С к треугольному виду, здесь такова: - -
К =
-0,9317 L-0,3632
,3632 1 ,9317 J '
-0,3632
о
Конечно, при выполнении алгоритма LSE (см. (20.24)) зту матрицу обычно не вычисляют в явном виде. Теперь в соответствии с формулами (20.19) - (20.23) получаем
С,
-0,4386 ,,0,5285 -0,7049
0,0
0,1714 0,0885
МЛ
У i
0,1376
= -0,3137, /
Г-1,17751 [ 3,8848 J
Г 0,4935"j ~ [ 0,7455 J'
у2 =4,0472,
-0,4386 .
(20.29)
Рассмотрим теперь некоторые теоретические следствия теоремы 20.9.
Формулу (20.10) можно записать в виде х = А Ь, если положить b = I I и
А* = [C*-(EZyEC+:(EZ)*]=[C*-K2(EK2YEC+:K2(EK2y]. (20.30)
Но (20.30) означает, что х есть нормальное псевдорешение зада-чи min \\Ах - Ь \\, где А — матрица, псевдообратная для матрицы А , опре-
деленной в (20.30).
Л +
Теорема 20.31. Псевдообратная для матрицы А , определенной в (20.30), имеет вид
¦а-
(2032)
где
,(20.33)
Е = (EZ)(EZ)*E = E(EZ)*E = ЕК2(ЕК2)*Е,
a Z и К2 определены так же, как в теореме 20.9. Доказательство. Напомним, что
ск2=о, к1с*=о,
K2K2=In_mi, Z = /„ - С С-К2К2 , (EZ)* = (ЕК2К1У=К2(ЕК2)\
Из этих соотношений прямо следуют другие, также используемые в доказательстве:
EZC* = ЕК2К\С* = О,
С(ЕгУ=СК2(ЕК2У = 0,
E(EZ)* = ЕК2(ЕК2)* =
= EK2KlK2(EK2y = (EZ)(EZ)*. (20.34)
Равенство (20.34) устанавливает тождество различных выражений для Е в (20.33).
109
Положим теперь
*-[ ' 1
. (?Z)(?Z)+?J и проверим четыре условия Пенроуза (теорема 7.9).
1. А*Х = СС - (?Z)+?C*C + (?Z )+(?Z)(?Z)+? = = СС - (EZ)*E(C*C - I) = C*C + (?Z)+(?Z).
Полученная матрица симметрична.
Г CC*-C(EZ)*EC* C(EZY 1
2.XA* =
|_(?Z)(?Z)+?[/-(?Z)+?]C+ (EZ)(EZYE(EZy J
[CC* 0 "I
0 (EZ)(EZ)* J '
Полученная матрица симметрична.
3. A *XA + = [C+C + (EZ)\EZ)][C*-(EZ)*EC*: (EZ)*] = = iC* - (EZ)\EZ)[I - (EZ)*E)C*: (?Z)+(?Z)(?Z)+} =
= [C* - (EZ)\EZ)(EZyEC : (EZ)*] = = [C* - (EZ)*EC*: (EZ)*] = A*.
4.XA*X = I + ] ¦ [C+C + (?Z)+?Z] =
L (EZ)(EZ)*E J J
¦ f ' 1 =
L (EZ )(EZ )*EC*C + (EZ)(EZ )*E(EZ )*EZ J
[(?Z)(?Z)+?[C+C + Z] ] ~ [ (EZ)(EZ)*E j ~ *'
Теорема 20.31 доказана.
В качестве числовой иллюстрации к теореме 20.31 вычислим матрицы (20.32) и (20.33) для задачи (20.25) - (20.28). Из (20.33) имеем
Г 0,1714 1
Е = (ЕК2)(ЕК2)Е = ¦ [4,6076 2,37871 X
L 0,0885 J 1 '
Г 0,4302 0,3516 1 _ Г 0,5943 0.41551 [ 0,6246 0,3384 J ~ I 0.3068 0,2145 ] '
110
аиэ (20.32) находим
0,4087 0,5943 0,3068
0,1593 0,4155 0,2145
Согласно теореме 20.31, полученная матрица обладает следующим свойством. Для произвольного одномерного вектора d и произвольного двумер-
ного вектора / решение задачи наименьших квадратов ЛдсЫ _ I являет-
ся в то же время решением такой задачи НКУ: минимизировать \\Ex-f || при условии Сх = d, где С и Е указаны в (20.25) и (20.26). Нужно отметить, однако, что нормы невязок для этих двух задач наименьших квадратов в общем случае неодинаковы.
