Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 36

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 36)

Линейная комбинация в правой части называется линейной,иатематической моделью. Задача состоит в том, чтобы выбрать п коэффициентов с„..., с„таким образом, чтобы модель в том или ином смысле согласовывалась с данными. Модель линейна, потому что коэффициенты входят в нее линейно; однако базисные функции могут быть нелинейными функциями от г. Наиболее распространенной линейной моделью является полином у (() ж с, +с,г — , 'с„ге+... +с„г" '. Он получается, если взять ср;(1)=Р ', хотя, как мы увидим, более подходящими могут оказаться иные базисные полиномы. Среди других примеров — тригонометрическое приближение уЯжс,з!п (+с,яп 2(+...+с„яп пг, где грэ(1)=яп /1, и экспоненциальное приближение с фиксированными экспонентами у (1) ж с,ех '+... + с„е'л', зь выэлвнивзние данных 211 в котором ф1(г)=ехр(х;1) для заданных )ч, (еслн нужно определять также и 1ь то это превращается в нелинейную модель.

См. ~ 8.5 н упр. 9.3.) Мы будем рассматривать случай, когда число т заданных точек больше нли равно числу и неизвестных коэффициентов. В этом случае задача выбора коэффициентов переопределена, и обычно не удается построить модель, точно удовлетворяющую данным, т. е. интерполнрующую их. Из многих различных критериев для определения коэффициентов с, наиболее часто используется метод наименьших каадраглса. Для л1обого выбора коэффициентов с; невязка в 1-й заданной точке равна г, = .,"., с,ф, (1,) — уг. 1=1 Критерий наименьших квадратов требует, чтобы с1 выбирались из условия минимального значения для суммы квадратов невязок; т.

е. минимизировать,)' го с. К=1 Если модель может точна удовлетворить данным, то этот минимум будет нулем, так что интерполяция включается сюда как специальный случай. Критерий наименьших квадратов необязательно определяет единственный набор коэффициентов. Если базисные функции линейно зависимы в заданных точках, что означает существование коэффициентов у,, среди которых есть ненулевые, таких, что л ~~' у фу(11).=0, (=. 1, ..., гп, /=! то к коэффициентам сг можно прибавить любое кратное коэффициентов уь не изменяя сумму квадратов невязок.

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

Одна из возможностей — это применение математического анализа. Пусть г=- ~,~, с,ф, (1,) — у,. 9. НАИМЕНЬШИЕ КВАДРАТЫ 212 Наша цель — минимизировать г или, что все равно, минимизировать г', потребуем, поэтому, чтобы для й=), ..., и д㻠— =О. дс» Беря производные и изменяя порядок суммирования, получаем Это система из и линейных уравнений с и неизвестными с,. Ее можяо записать в матричной форме Рс=о, где р»х= Х !Р»(г ) !Р~(~ ) !'= ! у» = Х %» ((!) у" Например, при аппроксимации в смысле наименьших квадратов посредством прямой у(Ожс!-~-с»( имеем Уравнения Рс=д называются нормальными уравнениями. Заметим, что матрица Р зависит лишь от базисных функций; значения у; в нее не входят.

В принципе нормальные уравнения можно решать, используя подпрограммы ОЕСОМР и ЗОРЧЕ из гл. 3. Однако, поскольку р»; — — р;ы матрица Р симметрична, и время и память, требуемые для ОЕСОМР, могут быть сокращены вдвое. Более того, можно показать, что Р положительно определена, и потому не требуется выбор ведуших элементов. Следовательно, используя вариант гауссова исключения, рассчитанный на положительно определенные симметричные матрицы, можно решать нормальные уравнения с менее чем половинными затратами по сравнению с РЕСОМР и БОГАЧЕ.

Однако есть серьезные, фундаментальные доводы против использования нормальных уравнений. Оказывается, что матрица Р часто имеет очень болыпое число обусловленности; поэтому каким бы методом ни решались нормальные уравнения, а г. вьп запивания данных ошибки во входной информации н ошибки округлений, внесенные в процессе решения, чрезмерно преумножаются в вычисленных коэффициентах. В крайней ситуации, когда базисные функции гр,~г) линейно зависимы, можно показать, что матрица Р вырождеиа, и число обусловлеяности может рассматриваться как бесконечное.

Следовательно, методы, избегающие высокого числа обусловленности, связанного с нормальными уравнениями, есть в то же время методы, способные обнаруживать линейную зависимость среди базисных функций. Гауссово ясключение и его варианты не слишком хорошо приспособлены к выявлению такой зависимости. Наша оценка числа обусловленности в какой-то мере помогает, однако она может лишь сигнализировать об опасности, но не предложить лекарство. Наиболее надежный метод для вычисления коэффициентов в обцей задаче наименьп1их квадратов основан на матричной факторизации, называемой сингулярным разложением. Есть другие методы, требующие меньше машинного времеви и памяти, однако онн менее эффективны в том, что касается учета ошибок заданной информации, ошибок округления и линейной зависимости.

Сингулярное разложение, или Я1Р гг, подробно описывается в последующих параграфах этой главы. Однако, чтобы испольэовать ЯгР в практическом выравнивании наименьшими квадратами, совсем не обязательно понимать этн параграфы во всех деталях. Метод Яг'Р начинается с составления матрицы, известной в статистическом анализе экспериментов как матрица алана. Это прямоугольная матрица из гп строк и а столбцов, элементы которой суть аг1=гр,(1г).

Если через у обозначить вектор размерности т с элементами уь а через с — вектор размерности гг с компонентами сп то приближенные равенства и ~ сггр,()г) уг, 1==1, ..., гп, 1=1 можно переписать в виде Асжу. Подпрограмма Я1Р, приведенная в конце главы, исходя из входной матрицы А, получает на выходе трн матрицы Х, У н )г. Матрица Х вЂ” диагональная с неотрицательными диагональны- ") От Мпяи!аг еа1ие дееогпроац1оп,— Приап перее.

К НАИМЕНЬШИЕ КВАДРАТЫ ми элементами, называемыми сингулярными числами матрицы А. Матрицы У и 1' используются для преобразования уравнений Асжу в эквивалентную диагональную систему г,ежу. Пусть оп 1=1,..., и,— диагональные элементы г.. В принципе если все аз отличны от нуля, то можно разрешить преобразованные уравнения, полагая уу с = —, /=-1, ...,п.

ат ' Однако на практике это не всегда желательно, если некоторые а; малы. Оказывается, что все пз не равны нулю тогда и только тогда, когда базисные функции <р~ линейно независимы в заданных точках. Поэтому ключ к правильному использованию Я~0 — это введение границы т, отражающей точность исходных данных и точность используемой плавающей арифметики. Всякое пп большее, чем т, приемлемо, и соответствующее с; вычисляется как у;(пь Любое ап меньшее, чем т, рассматривается как пренебрежимо малое, и соответствующему с; может быть придано произвольное значение. С этой произвольностью значений связана неединственность набора коэффициентов, получаемых методом наименьших квадратов.

Изменения входных данных и ошибки округлений, меньшие, чем т, могут привести к совершенно другому набору коэффициентов, определяемых этим методом. Поскольку обычно желательно, чтобы эти коэффициенты были по возможности малы, то полагаем с,=О, если аз(т. Отношение а,„/а ы, где и,„— наибольшее, а о.,„— наименыпее ненулевое сингулярное число, можно рассматривать как число обусловленности матрицы А. Это не то число обусловленности, которое было введено в гл.

Э, но его свойства во многом те же самые; обычно и порядок величины у него тот же. Как мы увидим в следующем параграфе, для задач на наименьшие квадраты оно является более подходящей мерой обусловленности. Отбрасывание чисел о,,меньших, чем т, приводит к уменьшению числа обусловленности до о ,„(т. Поскольку число обусловленности является множителем в увеличении ошибки, то следствием будет более надежное определение коэффициентов с;. Цена за эту возросшую надежность — возможное увеличение невязок, вл.

Характеристики

Список файлов книги