Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 17
Текст из файла (страница 17)
аз, Чтобы снмметрнзовать полученную систему уравнений, этн последние два уравнения' нужно умножить соответственно на йг' и — й'„и что дает — Ьгог + (11 о, = — йзЛ1"' н й„,о„, — й„,о„= — Ь„' 1Л„"'з. Для сплайна с этими граничными условиями коэффициенты о;, таким образом, удовлетворяют следующей системе из и линейных уравнений с и неизвестными: и бЛгзг Итак, мы требуем, чтобы ог ог Лгзг И 1 й, 0 0 Ь, 2(й,+Ь,) Ь 0 О 0 й, 2(Ь1+ Ь~) А~ йгЛ <11 Л,— Ь, Лз — Лг 4 интеРполяггия а, л1 422 ~2 а, й! о, О здесь диагональные элементы а; вычисляются по формулам а, =- — 12„ аг -2(ггг, +гг!) — — „' ', г — — 2, 3,..., л — 1, 1-1 2 г!!! а =- — й а О 1 а правые части р! — по формулам гг й24!24 аг ' а„ Наконец, коэффициенты о; определяются посредством обратной подстановки: Р.
а„' п — 1,п — 2,...,1, о„= рг — г!гл Эту систему из п уравнений можно решить методом исключе. ния. Для вычисления неизвестных о; можно было бы использо. вать подпрограммы ОЕСОМР и КОРЧЕ. Однако матрица козф. фицпентов имеет несколько специальных свойств: 1. Матрица трехдиагональная. 2. Матргща симметричная. 3. При любом выборе х,(хг(...(х„матрица певырожденная и диагонально доминирующая.
Следовательно, всегда существует единственное решение о„... о„. Можно показать также, что для любого разумного выбора точек х„х„..., х„матрица коэффициентов хорошо обусловлена. Основываясь на этом и на свойстве диагонального доминирования, можно ожидать, что применение гауссова исключения без масштабирования и без выбора ведущих элементов позволит тем не менее получить решение с хорошей точностью. Гауссово исключение приводит исходную систему к верхней треугольной форме: сз. подпРОГгхммы $Рь1на н зачхь 9! В некоторых приложениях желательно хранить о; и использовать их непосредственно для вычисления сплайна.
Однако если сплайн нужно вычислять многократно, то стоит переупорядочнть члены. По разным причинам предпочтительней вычислить и сохранять коэффициенты Ь;, с; и д! в кубическом представлении з(х)=у!+Ь;(х — х;)+с!(х — х!)"-+с(!(х — х )', х, (х(х!~„ на каждом подынтсрвале (хп х;„), 1=1, 2,..., и — 1.
Эти коэффициенты выражаются формулами с; =-- Зо!, я~+1 и! ! 1- 1, 2, ..., и — 1. Использование такой формы хранения сплайна упрощает операции с ннм, например вычисление производных и интегралов. ИЛЛЮСТРИРУЮЩАЯ ПРОГРАММА ДЛЯ ПРОГРАММ БРЫМЕ И ЕЕНАЕ С С ЯЕА1. 5, О, БЕНАЕ 1МТЕОЕК 1, !Ч Х=!О РО! 1=1,!Ч 4.в.
Подпрограммы ЕР).ИчЕ м ЕЕЧАЬ Метод вычисления параметров кубической сплайн-функцин, обсуждавшийся сейчас, реализован в подпрограмме 5РПЬ(Е. Комментарии в программе описывают ее использование. В процессе исключения в массивах В, С и й хранятся величины аь (3! и 1!; (см. предыдущий параграф). С помощью подпрограммы-функции 5ЕНАЕ можно вычислять значения сплайна после того, как его коэффициенты были определены подпрограммой ЗРЕ1ХЕ. Если по сравнению с предыдущим вызовом независимая переменная (у уже не находится в том же интервале, то для разыскания нужного интервала применяется двоичный поиск. Читателю, не слишком хорошо знакомому с двоичным поиском, мы настоятельно советуем просчитать несколько примеров на руках.
Разумеется, двоичный поиск не является наилучшим для всех случаев способом (почемур), Приводимый ниже простой пример демонстрирует обращение к подпрограммам 5РПХЕ н 5ЕЧАЕ. На выходе будет получено: 2.50000 15.62500. (Почему?) УПРАЖНЕНИЯ УПРАЖНЕНИЯ 4.!. Постройте и=-! ! тачек, полагая уг=ег1 (х;), ) Значения функции ег! можно взять из имекяцихся таблиц либо вычислить ка своей машине по соответствующей подпрограмме. С помощью подпрограммы БРЕ!)4Е найдите коэффициенты кубического сплайна, ннтерполирующего этн точки. С помощью подпрограммы БЕАгЛЕ нычислнте сплайн в промежуточных точках и сравните значения сплайна со значениями функции ег1. Какова максимальная ошибка для этих промежуточных точек? 4.2. Используя подпрограммы БРЕ!НЕ н ВЕЧЛЕ, праинтерполируйте функцию Рунге ! 1+ 2бхз Нвееяеике Гаа 75 994 575 91 972 266 105 710 620 123 203 000 131 669 275 150 697 361 179 323 175 203 211 926 1900 1910 1920 1930 1940 1950 1960 1970 а) Поскольку здесь восемь точек, имеется еднкствепный полинам степени 7, интерполнрующий эти точки.
Однако некоторые способы представления этого полппоыа с вычислительной точки зрения предпочтительней других. Вот четыре по точкам х;=- — ! .О, — 0.9,..., 0.9, 1.О; и=21. Сравните результаты с поляномом 20.й степени, ннтерполирующнм те же точки. 4.3. Переделайте подпрограмму ВРШМЕ так, чтобы она находила коэффициенты естественного кубического сплайна, т. е. сплайна с граничными уело. виями з" (хз) — — в" (к„)=-О. Переделка понадобится весьма существенная, по. скольку, помимо йрочего, теперь будет только и — 2 неизвестных коэффициента Ьп Нужно лн переделывать и подпрограмму ЗЕМЛЕ? 4.4.
Сравните естественный сплайн со сплайнам, построение которого описано в 4 4.4. Именна, постройте тестовый пример, беря в качестве кп 1= 1,... ..., и, п равноудаленных точек на ннтернале [О, п) (в это число входят н концевые точки), а в качестве д! числа соэ хп Вычислите коэффициенты сплайна по подпрограмме ВРЕ!7(Е в ее исходном варианте. Вычислите также коэффициенты по подпрограмме 3РЕ!)(Е, переделанной в соответствии с упр.
4.3. Сравните две различные функции в (х) с саз х для значений к, не совпадающих с зада иными точками, Особое внимание обратите на значения вблизи концов интервала. Пра. делайте это для нескольких значений и, например !О, 20 и 30. Почему в этом упражнении нужно брать именно сов х, а не Мпх? 4.5. Следующие данные Бюро переписей показывают население Соединенных Штатов: к ИНТЕРПОЛЯЦИЯ возможности; в каждом случае 7 изменяется иа интервале !900 ~т~!970: 7 ~~~~ л?77, ,=а 7 ~~„ат (7 — 1900)7, т=е 7 ~„с (! — 1935)У, 7 О ~~; „~1 — !986У' Во всех случаях коэффициенты находятся из системы уравнений 8-го порядка, но матрацы этих систем весьма различны. Постройте каждую нз четырех матриц и вайдите оценки нх обусловленности, пользуясь подпрограммой ОЕСОМР.
Затем по подпрограмме 801.ЧЕ определите коэффициенты. Проверьте, хорошо ли каждое представление воспроизводит исходные данные. б) Проинтериолируйте данные точки нолиноыом 7-й степени, пользуясь представлением с наилучшей обусловленностью, найденным в задании а), а также кубическим сплайнам, вычисляя его по подпрограмме ЗРЕ1НЕ. Протабулируйте полученные функции за период с 1900 но 1980 г.
с интервалом в 1 г и нарисуйте нх графики. Вы обнаружите, что обе функции очень хорошо согласуются до !970 г., но их поведение между 1970 и !980 г. совершенно различно. Какой нз двух подходов прелсказыаает, что до 1980 г. наступит момент с нулсзыж ростом населения? Если вы выполняете это задание после того, как опубликованы данные переписи 1980 г., проверьте, какой способ дает более точный прего. в) Переделав подпрограмму ЗРЕ1НЕ так, чтобы ова использовала естест. венные граничные условна, выясните, как это изменение влияет на прогноз с 1970 по 1980 г. Поскольку прн егтественных граничных условиях сплайн вне заданного интервала считается линейной функцией, то нулевой рост населения не может быть предсказан. 4.6.
Обозначим через Р(х) полипом степени п, такой, что Р(й)=й?й+1 для й=-0, 1,..., л. Найдите Р(л+1). Указания: рассмотрите отдельно случаи четного и нечетного а. Если вы не сможете найти аналитическое решение, используйте машину. (Зта задача, разумеется, без указаний, входила в число задач Четвертой математической олимпиады для учеников средних школ ОША.) 4.7. В ходе вообрзжаемога химического эксперимента получены следующие семь пар данных (их ошибками можно пренебречь): с ~ -!.000 -0960 -0.860 -0.790 0.770 0.600. 0.980 у 1 -1.000 — 0.18! ай94 0.986 0.898 0.800 -0.Зоб Г Нужно оценить значения у (1) для 1, находящихся между — 1.000 и 1.000, по. средством интерполирования по данным точкам. Предполагается, что у(7)— очень гладкая кривая.
а) Нанесите точки на график н проведите гладкую ннтерполирующую крн ную по интуиции. б) Найдите(единственный) полипом 6-й степени, интерполнрующнй данны~ точки, н начертите его график. Хорошо ли отражает полипом характер нз л~енения данных? УПРАЖНЕНИЯ в) По подпрограмме БРИКЕ найдите коэффициенты кубического сплайна, ннтерполирующего данные точки. По подпрограмме БЕ(ГАЕ найдите значения сплайна в достаточном числе промежуточных тачек, чтобы начертить его гра. фик. Хорошо ли отражает сплайн характер изменения данных? (Мы призна. тельны Ричарду Ф Томпсону, предложившему згу задачу).
4.8. Сколько плавающих умножений, делений н сложений или вычитаний выполниется подпрограммой ЯРЕ(?(Е? Каково общее число плавающих операций? Выразите ваши результаты функциями ат )У. 4.9. Лля случая равноудаленных узлов (т. е. 81=6, 1=1, 2,..., л — 1) алгоритм, реализованный в 3Р! 1)ЧЕ, можно упростить. Каков алгоритм для равноудаленных узлов? Сколько плавающих операций в нем требуется? Загляните в упр. 3.7. гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
