Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 43
Текст из файла (страница 43)
Выходом будут сингулярные числа (обычно, хотя и не обязательно, в убывающем порядке), ту,п-матрица (7, если ояа заказана, и икр-матрица У, если она заказана. В случае большой задачи лнэбую из матриц () и можно формировать на месте матрицы А. Статья Голуба и Райнша указывает, что процедуру легко можно модифипировать таким образом, чтобы получить полную тки-матрицу (7. Приводимая ниже иллюстрирующая программа основана па примере, которым мы пользовались всюду в этой главе. Сингулярные числа суть 35.)27223, 2.465397 и 0.000000.
Матрицы (/ и К приведены в 3 9.2. Вычисляются лишь три первых столбца матрицы (7; на некоторых машинах знаки столбцов обеих матриц (7 н $' могут быть иными. С ИЛЛЮСТРИРУЮЩАЯ ПРОГРАММА ДЛЯ ПОДПРОГРАММЕ! 5НО С КЕА(. А(5, 3), 11(5, 3), Н(5, 3), 5!СМА(5), АНОКК(5) 1МТЕОЕК 1, ! ЕКК, 3, М, Х, )(М )ЧМ =5 М=-5 И ==3 )301 1=-1, М ))О! 3=1, М А(1,,1) =1+(3 — П*М СОМТ1МИЕ СА1.1.
5НО(ММ, М, М, А, 510МА, .ТРОЕ.„(), .ТК1)Е., Н, 1ЕКК, 1 %0К К) 1Е(1ЕКК.МЕ.О) ЪК1ТЕ (б, 2) 1ЕКК 2 РОКМАТ (15Н ТКО()В! Е 1ЕКК =,14) ))О 3 3 =-1,М %К!ТЕ (6, б) 510МА ()) 3 СОХТ1МОЕ %К1ТЕ (б, 7) ))О 4 1=1, М %К!ТЕ (6, б) (Н(1, 3), 3 =1, Х) 9.5. Г!ОДПРОГРАММА 5РО 251 % СОДЕР)КИТ Н (НЕОТРИЦАТЕЛЬНЫХ) СИНГУЛЯРНЫХ чисел л (дилгонлльных элементов з). они не УПОРЯДОЧЕНЫ. ЕСЛИ ПРОИСХОДИТ ВЫХОД ПО ОШГ!БКЕ, ТО ДЛЯ ЗНАЧЕНИЙ ИНДЕКСЛ 1Ейй )- 1, !Ейй-,'-2, ..., М СИНГУЛЯРНЫЕ ЧИСЛА ДОЛЖНЫ БЬ|ТЬ ВЕРНЫ. Н СОДЕРЖИТ МАТРИЦУ (! (С ОРТЕ)ГОНАЛЬНЫМИ СТОЛБЦЛМИ) ИЗ РАЗЛОЖЕНИЯ, ЕСЛИ ДЛЯ ПАРАМЕТРА МЛТН БЫЛО ЗАДАНО ЗНАЧЕНИЕ .ТКОЕ.
В ПРОТИВНОМ СЛУЧАЕ 0 ИСПОЛЬЗУЕТСЯ КАК ВРЕМЕННЫЙ МАССИВ. () МОЖЕТ СОВПАДАТЬ С А. ЕСЛИ ПРОИСХОДИТ ВЫХОД ПО ОШИБКЕ, ТО СТОЛБЦЫ (), СООТВЕТСТВУЮШИЕ ИНДЕКСАМ ВЕРНЫХ СИНГУЛЯРНЪ|Х Ч)!СЕЛ, ДОЛЖНЫ ТАКЖЕ БЫТЬ ВЕРНЫ. ч содейжит млтйиц| у у (ойтогонлльную) из РлзлоЖЕНИЯ, ЕС.ЧИ ДЛЯ ПЛРЛЛ(ЕТРА МАТУ БЫЛО ЗАДАНО ЗНАЧЕНИЕ .Тй()Е.
В ПРОТИВНОМ СЛУЧАЕ НЛ У НЕ ПРОИЗВОДИТСЯ ССЫЛОК. 7 ТАКЖЕ МО)КЕТ СОВПАДАТЬ С Л, ЕСЛИ () НЕ ВЪ|ЧИСЛЯЕТСЯ, ЕСЛИ ПРОИС- ходит выход по ошиБке, то столБцы ч, соот- ВЕТСТВУЮЩИЕ ИНДЕКСАМ ВЕРНЫХ СИНГУЛЯРНЫХ ЧИСЕЛ, ДОЛЖНЪ| БЫТЬ ТЛКЖЕ ВЕРНЫ. 1ЕКК РЛВНО НУЛЮ, ЕСЛИ ПРОИСХОДИТ НОРМАЛЬНЫЙ ВЫХОД ИЗ ПОДПРОГРАММЫ, К, ЕСЛИ К-Е СИНГУЛЯРНОЕ ЧИСЛО НЕ БЫЛО ОПРЕДЕЛЕНО ПОСЛЕ 30 ИТЕРАЦИЙ. КУ| — ЭТО МЛССИВ ПРОМЕЖУТОЧНОГО ХРАНЕНИЯ. ВОПРОСЫ И КОММЕНТАРИИ НУЖНО НЛПРЛВЛЯТЬ ПО ЛдРЕСУ В. 3. ОАКВ0%, ЛРРЬ|ЕРМЛТЕМАТ!СЗ Р!У!3!ОР(, ЛКООМКЕ МАТ10НАЬ 1ЛВОКЛТОКТ ПОДПРОГРЛММЛ МОДИФИЦИРОВЛНА С ЦЕЛЬЮ ИСКЛЮЧИТЬ ПЕРЕМЕННУЮ МАСНЕР 1Ейй =-0 РО |00 ! =-1, М РО 100,1 =- |, Н 1)(1, !)=Л(1, З) 100 СОХТ1КЦЕ ХЛУСХО.'|ДЕРОВО ПРИВЕДЕНИЕ К ДВУХДИАГОНЛЛЬНОЙ ФОРМЕ ...... О=О. 0 БСЛ|.Г..
С О АХОКМ = О. 0 РО 000 1==-1, Н 1. - -! .,'- ! КЧ!(!) =-БСЛЬЕ*О О=О. 0 Э. НЛИМВНЬШИВ КВЛДРЛТЫ Т)(Л (И=- Х*С вЂ” -2*5 Лг(3, 1).= — Х*5+ Х'С СОНТ!М'Е 570 С Х =5()йТ(Г*Р+ Н*Н) ТУ(!1) =г ......ВРА(ЦЕНИВ МОЖЕТ БЫТЬ ПРОИЗВОЛЬНЫМ, ЕСЛИ Х РАВНО НУЛЮ...,,, 1Г (Х.ЕО. О. О) ОО ТО 580 С=.Р!Х 5.= Н7Л Г =С"О+ 5*У Х = — 5'О .-С*"г' 1Р ( НОТ. МАТ(1) ОО ТО 600 57.
580 1)0 590 ) =-1, М УГ -01(Л !И 7=1'(Л 1) ()(), 11) =- У'С+7*5 И(Г, 1) = — Уь5-~-Х"С ЗЗЕ 590 СОН Т(гч С 600 СОНТ(!Ч(/Е С УПРАЖНЕНИЯ 9.1, постройте 11 точек, беря г;=(1 — !) г10 и р;=.ег1(Й), 1=1,, .., 11. Функцию ег1(0 можно вычислять посредством любого иэ методов, описанных в упр. 1.1, 5.1 или 6.1. (а) Выровняйте эти точки в смысле наименьших квадратов, берн полиномы со степенями от 1 до 1О. сравните построенные полнномы с ег1(г) для ряда промежуточнык (по отношению к исходным) значений Г и исследуйте зависимость максимальной ошибки от числа л коэффициентов палинома. й)г1(Ь) =0.0 йЧ!(К) = — Р ТУ(К) = Х ОО ТО 520 С ......СХОДИМОСТЬ...... 650 1Р(2. ОЕ. О.
О) ОО ТО 700 С ......ТЧ(К) ДЕЛАЕТСЯ НЕОТРИЦАТЕЛЬНЫМ. ° ° ° .э %(К) =- — 2 1Р(.НОТ. МАТУ) ОО ТО 700 С ОО 690 3=1, Н 690 У(Л К)=- — У(Л К) С 700 СО!чТ! Н()Е С ОО ТО 1001 С ......УСТАНОВИТЬ ЗНАЧЕНИЕ ПРИЗНАКА ОШИБКИ— С ПОСЛЕ 30 ИТЕРАЦИЙ НЕТ СХОДИМОСТИ К СИНГУЛЯРНОМУ С ЧИСЛУ....,. 1000 1Ейй = К 100! йЕТийй ЕНО УПРАЖНЕНИЯ 257 (б) Поскольку ег1(Г) — нечетная функция Г, т. е ег((Г)=- — ег1( — 1), то разумна для выравнивания тех же точек применить линейную комбинацию нечетных степеней (: еН (г) = с,г+сг(з+... -)-си(зч Снова исследуйте, как ошибка в промежуточных точках зависит от п. Так как 1 а этой задаче ограничено интервалом (О, 1), то нет необходимости в использовании других базисных полнномов.
(в) Палвномы не слишком хороши н качестве приближающих функций для ег1(1), потому что они не ограничены при растущем 1, в то время как ег((() асимптотически стремится и !. Поэтому при тех же точяах испробуете модель вида ег1 (1) гз с,+е™ (с,,- саг+с,г'+с,г'), где г.— 1,'(1+1). Как выглядит ошибка в промежуточных точках в сравнении с полиномиальнымн моделямиг (г) Возьмите ту же модель, что и в и. (в), но для ! а=в !+Л( ' где Л вЂ” нелинейный параметр, который можно найти, используя подпрограмму ГМ!М, как это описывается в упр. 9.3. 9.2.
В упр. 4.7, где задано т.==7 точек, примените выравнивание посредст. вом полииомов со степенями от 0 до 6. Начертите полученные палиномы,' равно как н сплайн, интерполирующнй эти точки. 9.3. Раздвгимыа наименьшие квадраты Предположим, что т точек (10 у,), 1:=. 1,..., гп, нужно выравнять в смысле наименьших квадратов посредством следующей функпии от Г: У (1) = ос+ сг! + овгз+счсхг. Эта функция содержит пять параметров: с,, с„сз, с4 и Л, Четыре коэффициента с; входят линейно, а коэффициент Л входйт нелинейным образом. Пусть А (Л) — матрица размера тм 4 с элементами ш .
и! т= — с Пусть у — вектор порядка т, составленный нз заданных значений уб а с— вектор из четырех неизвестных коэффициентов с . Мы получаем тогда такую оптимизационную задачу: ш1п шш ( г( (Л) с — у)г. А с Внутренний минимум, зависящий оз четырех линейных параметров, можно найти для любого А по подпрограмме 5ЛгП, Внещнии минимум, зависящий от единственного нелинейного параметра Л, можно находить, используя подпрограмму РМ155 Заметим, чта к 5УП абращаетси подараграмма-функция, вызываемая программой РМ!55 Вот два набора данных, к которым нужно применить этот метод. В первом случае ие должно встретиться трудностей, но второй набор приводит к вырождению, которое можно вынвитгч контролируя величину внутреннего минимума и сингулярные числа матрицы А (л! Найдите значения с.
и Л, которые дают наилучшее приближение Единственны ли коэффициенты с г Считайте, чта данные вертя лишь в двух десятичных знаках после запятой, так что уг могут иметь ошибки, достигающие 0.005. з и «1!ыцньшие кв «дпкты 256 У У. Первый второй набор набор 20.00 24.!3 26. 50 27. ! 3 26к!О 23.13 1В.50 12.!3 4.00 0.0 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 20.00 5 !.56 68.73 75.46 74.36 67.09 54.73 37.98 17.26 ') Иго дскоднруется кзк 1БМ.— 7?рим. пере», 9.4.
(а) Выровняйте данные переписей из упр. 4.6,пользуясь полиномами Различных степеней. Используйте полученные приближения для прогноза численности населения в 1960 г. Как влииет на прогноз численности населения ваш вьбор базисных поливанов? Л выбор границы для пренебрежимо малых сингулярных чисел? Л точность арифметики, если у вгс есть выбор? (б) Выровняйте те же данные переписей пс<редствсм модели у(Г) - с,-! «»(à — 1900)+с»е с переменным Х в соответствии с упр. 9.3.
Предскажите численность населения в 1960 г. (в) Попробуйте прибтизить данные переписей квадратичным полиномом у (!) = с, +с,?-- Г используя нормальные уравнения. Каково число обусловленности полученной матрицы? Каков прогноз численности населения на !с»60 г.з 9.5. Сингулярный анилиз криптгграмм Эта задача основана на статье Моулер, Моррисон (1977). Цель — отделить гласные от согласных в кодированном сообщении. Пусть кто.нибудь приготовит для вас криптограмму, взяв текст из нескольких сотен знаков, опустив в ием пробелы и знаки препинания и выполнив простую взаимно-однозначную подстановку букв Например, пусть исходный текст был такой: НО!Ч 15 ТНЕ Т!МЕ РОВ МЕН 10 А!Р ТНЕ!К СОЕМТЙУ.
Используя код «2001», в котором каждая буква заменяется своей предшественницей в алфавите (вспомните, что компьютер в фнльле Стэнли Кубрика «200!» именовался НАС'), получим кодированное сообщю,ие ММ3«НЙ5ОР5Н!гРЕВ)(«)СРМ5)«)2НС5ОРНЯВМТМ5ЯХ. Напишите программу, которая обрабатывает подобные тексты н формирует матрицу размера 26к26, элементы которой естественней индексировать не целыми числами, а буквами. Элемент (к, у) указывает, сколько раз в кодированном тексте встретилась пара «Х У». В данном примере ам н=. 1, а» „=. 1,... ..., а, =-2 и т д.
При этом нужно считать, что последняя буква текста сопровождается первой, так что а м=-1. Эта матрица называется матрипгй частот диграфа Вычислите 5НР для матрицы:астот днграфа нашего текста. Выведите компоненты столбцов СГ и У, соответствующих наиболывему сингулярному числу. Как правило, это компоненты первых столбцов и„, и «„,, к=а, М..., г. Все ко«шонеьты »тих векторон должны иметь одинаковый знак УПРАЖНеНИЯ и быть примерно пропорциональнычи частотам отдельных букв. Таким образом, в некадированиом сообщении с типичным распределением букв компонента е будет наибольшей, компонента ! — следующей по величине и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
