![]() |
|
сделать стартовой | добавить в избранное |
![]() |
СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ |
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Математический факультет Кафедра прикладной математики ДИПЛОМНЫЙ ПРОЕКТ СИНГУЛяРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАчЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ Заведующий кафедрой прикладной математики Исполнил: Научный руководитель Владикавказ 2002 СОДЕРЖАНИЕВВЕДЕНИЕ 3 Глава 1. Метод наименьших квадратов 7 1.1. Задача наименьших квадратов 7 1.2. Ортогональное вращение Гивенса 9 1.3. Ортогональное преобразование Хаусхолдера 10 1.4. Сингулярное разложение матриц 11 1.5. QR–разложение 15 1.6. Число обусловленности 20глава 2. Реализация сингулярного разложения 25 2.1. Алгоритмы 25 2.2. Реализация разложения 27 2.3. Пример сингулярного разложения 29глава 3. Использование сингулярного разложения в методе наименьших квадратов 33 ЗАКЛЮЧЕНИЕ 38 ЛИТЕРАТУРА 39 ПРИЛОЖЕНИЕ 1. Исходные тексты программы 40 ПРИЛОЖЕНИЕ 2. контрольный пример 45 ВВЕДЕНИЕ Метод наименьших квадратов обычно используется как составная часть некоторой более общей проблемы. Например, при необходимости проведения аппроксимации наиболее часто употребляется именно метод наименьших квадратов. На этом подходе основаны: регрессионный анализ в статистике, оценивание параметров в технике и т.д. Большое количество реальных задач сводится к линейной задаче наименьших квадратов, которую можно сформулировать следующим образом. Пусть даны действительная m( –матрица A ранга k(mi (m, ) и действительный m–вектор b. Найти действительный –вектор x0, минимизирующий евклидову длину вектора невязки Ax–b. Пусть y – –мерный вектор фактических значений, x – –мерный вектор значений независимой переменной, b – коэффициенты в аппроксимации y линейной комбинацией заданных базисных функций (: . Задача состоит в том, чтобы в уравнении подобрать такие b, чтобы минимизировать суммы квадратов отклонений e=y–Xb, где X – есть так называемая матрица плана, в которой строками являются –мерный вектора с компонентами, зависящими от xj: каждая строка соответствует определенному значению xj. Коэффициенты можно найти решая нормальные уравнения . Покажем это. Возведем в квадрат выражение для е: . Это выражение имеет экстремум в точке, где . Следует отметить, что последнее выражение имеет в определенной степени формальный характер, т. к. решение нормальных уравнений, как правило, проводится без вычисления обратной матрицы (метод Крамера) такими методами как метод Гаусса, Холесского и т. д. Пример. Пусть заданы результаты четырех измерений (рис. 1): y=0 при x=0; y=1 при x=1; y=2 при x=3; y=5 при x=4. Задача заключается в том, чтобы провести через эти точки прямую таким образом, чтобы сумма квадратов отклонений была минимальна. Запишем уравнение, описывающее проведение прямой по результатам измерений. Мы получаем переопределенную систему: или Xb=y. Нам понадобится матрица X X и обратная к ней: Тогда решение b=(X X)-1X y по методу наименьших квадратов будет иметь вид Таким образом, оптимальная прямая задается уравнением Метод точечной квадратичной аппроксимации (метод наименьших квадратов) не предполагает, что мы должны приближать экспериментальные данные лишь с помощью прямых линий.
Во многих экспериментах связи могут быть нелинейными, и было бы глупо искать для этих задач линейные соотношения. Пусть, например, мы работаем с радиоактивным материалом. Тогда выходными данными у являются показания счетчика Гейгера в различные моменты времени . Пусть наш материал представляет собой смесь двух радиоактивных веществ, и мы знаем период полураспада каждого из них, но не знаем, в каких пропорциях эти вещества смешаны. Если обозначить их количества через С и D, то показания счетчика будут вести себя подобно сумме двух экспонент, а не как прямая: . (1) На практике, поскольку радиоактивность измеряется дискретно и через различные промежутки времени, показания счетчика не будут точно Рис. 1. Аппроксимация прямой линией.соответствовать (1). Вместо этого мы имеем серию показаний счетчика , и (1) выполняется лишь приближенно: Если мы имеем более двух показаний, m>2, то точно разрешить эту систему относительно C и D практически невозможно. Но мы в состоянии получить приближенное решение в смысле минимальных квадратов. Ситуация будет совершенно иной, если нам известны количества веществ C и D и нужно отыскать коэффициенты ( и (. Это нелинейная задача наименьших квадратов, и решить ее существенно труднее. Мы по–прежнему будем минимизировать сумму квадратов ошибок, но сейчас она уже не будет многочленом второй степени относительно ( и (, так что приравнивание нулю производной не будет давать линейных уравнений для отыскания оптимальных решений. Глава 1. Метод наименьших квадратов 1.1. Задача наименьших квадратов Задача наименьших квадратов заключается в минимизация евклидовой длины вектора невязок (( Ax-b ((. Теорема 1. Пусть А – m( –матрица ранга k, представленная в виде A=HRK (2) где H ортогональная m(m матрица; R – m( –матрица вида , (3) где: R11 – kxk–матрица ранга k; K – ортогональная kxk–матрица. Определим вектор . (5) Определим как единственное решение системы R11y1=g1. Тогда: 1. Все решения задачи о минимизации ((Ax-b(( имеют вид , где y2 произвольно. 2. Любой такой вектор приводит к одному и тому же вектору невязки 4. Единственным решением минимальной длины является вектор Доказательство. В выражении для квадрата нормы невязки заменим A на HRK в соответствии с (2) и умножая на ортогональную матрицу H (умножение на ортогональную матрицу не меняет евклидову норму вектора) получим . Из (4) следует Подставляя оба последних выражения в (7) получим Последнее выражение имеет минимальное значение при R11y1=g1, а в этом уравнении единственным решением является , так как ранг матрицы R11 равен к. Общее решение y выражается формулой имеем , что устанавливает равенство (3). Среди векторов наименьшую длину имеет тот, для которого y2=0. Отсюда следует, что решением наименьшей длины будет вектор . Теорема доказана. Всякое разложение матрицы А типа (2) мы будем называть ортогональным разложением А. Заметим, что решение минимальной длины, множество всех решений и минимальное значение для задачи минимизации ((Ax-b(( определяются единственным образом. Они не зависят от конкретного ортогонального разложения. При проведении разложения необходимо приводить матрицы к диагональному виду.
Для этого обычно используются два преобразования: Гивенса и Хаусхолдера, оставляющие нормы столбцов и строк матриц неизменными.1.2. Ортогональное вращение Гивенса Лемма. Пусть дан 2–вектор .Существует ортогональная 2(2 матрица такая, что: . Далее прямая проверка. Матрица преобразования представляет собой матрицу вращений 1.3. Ортогональное преобразование Хаусхолдера Применяется для преобразования матриц к диагональному виду. Матрица преобразования представляет из себя следующее выражение: , (9) или, если вектор v нормирован, т.е. используется вектор единичной длины . В обоих случаях H – симметричная и ортогональная матрица. Покажем это: , т.е. симметричность и ортогональность. В комплексном случае матрица . Предположим, что дан вектор х размерности m, тогда существует матрица H такая, что а ( = 1, при положительной первой компоненте вектора х и = –1, при отрицательной. Доказательство. Положим действительная матрица. Любую действительную матрицу можно привести в треугольному виду и получаем следующее: 1.4. Сингулярное разложение матриц Пусть X – матрица данных порядка xp, где >p, и пусть r – ранг матрицы X. Чаще всего r=p, но приводимый ниже результат охватывает общий случай, он справедлив и при условии r
Входные данные, задаваемые каждым примером, можно рассматривать как стомерный вектор. Процедура предварительной обработки состоит в ортонормировании системы векторов, задаваемых всеми примерами обучающего множества. Отметим, что при тестировании предобработка отсуствует. Все программы, кроме программыHopfield. В этом меню Вы можете задать следующие параметры метода обучения: Использовать MParTan Организация обучения Вычисление направления Способ оценивания Уровень УДАРА Использовать MParTan Все программы, кроме программы Hopfield. При построении метода обучения Вы пользуетесь следующей схемой: Использовать MParTan Да или Нет ↓ Процедура спуска ↓ Организация обучения Усредненная Позадачная Задаче номер ↓ Вычисление направления Случайный спуск Градиентный спуск ↓ Метод оценивания Метод наименьших квадратов Расстояние до множества ↓ Нейронная сеть Входными параметрами процедуры MParTan являются: 1. Начальная карта. 2. Процедура вычисления Направления спуска. 3. Локальное обучающее множество. 4
1. Итерационные методы решения систем линейных уравнений с неединственными коэффициентами
2. Численные методы решения систем линейных уравнений
3. Итерационные методы решения систем линейных алгебраических уравнений
4. Методы решения систем линейных уравнений
5. Графический метод и симплекс-метод решения задач линейного программирования
10. Метод непрерывных испытаний. Графический метод. Испытания на ремонтопригодность
11. Логико-интуитивные методы исследования систем управления. Метод тестирования
12. Линеаризация без метода наименьших квадратов
13. Метод наименьших квадратов в случае интегральной и дискретной нормы Гаусса
14. Применение методов линейного программирования в военном деле. Симплекс-метод
15. Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя
16. Решение задач линейной оптимизации симплекс – методом
17. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ПЯТИТОЧЕЧНЫМ МЕТОДОМ АДАМСА – БАШФОРТА
19. Анализ динамики внп методом линейной регрессии
20. Линейное программирование симплекс-методом Данцига
21. Решение задач линейного программирования симплекс методом
25. Решение задачи линейного программирования симплексным методом
26. Метод Гаусса для решения систем линейных уравнений
27. Графоаналітичний метод – "квадрат потенціалу"
29. Решение задачи линейного программирования симплекс-методом
30. Линейное программирование как метод оптимизации
31. Исследование природных ресурсов планеты с помощью космических методов
32. Исследование клеточного цикла методом проточной цитометрии
35. Обзор методов и способов измерения физико-механических параметров рыбы
36. Новейшие методы селекции: клеточная инженерия, генная инженерия, хромосомная инженерия
41. Государственное регулирование экономики: формы и методы
43. Нелегальная миграция в России и методы борьбы с ней
44. Предмет и метод гражданского права
45. Предмет, метод и система гражданского процессуального права /Украина/
46. Корпорация BBC. Формы и методы государственного контроля вещания
47. Формы и методы выхода предприятий на внешний рынок
48. Финансовый контроль: формы, методы, органы
49. Эффективные методы изучения иностранных языков
50. Метод действенного анализа в режиссуре театра, кино и телевидения
51. Соцреализм как метод искусства
52. Дидактические возможности отдельных методов обучения на уроках литературы в старших классах
53. Методы изучения музыкальных произведений крупной формы в старших классах общеобразовательной школы
57. Решение дифференциальных уравнений 1 порядка методом Эйлера
58. Оценка методов и средств обеспечения безошибочности передачи данных в сетях
59. Обзор возможных методов защиты
60. Метод деформируемого многогранника
61. Обучение начальных курсов методам программирования на языке Turbo Pascal
62. Модифицированный симплекс-метод с мультипликативным представлением матриц
63. Методы приобретения знаний в интеллектуальных системах
64. Билеты, решения и методичка по Информатике (2.0)
65. Вычисление определённого интеграла с помощью метода трапеций на компьютере
66. Интегрирование методом Симпсона
67. Защита цифровой информации методами стеганографии
73. Решение смешанной задачи для уравнения гиперболического типа методом сеток
74. Решение систем дифференциальных уравнений методом Рунге-Куты 4 порядка
76. Вычисление определенного интеграла методами трапеций и средних прямоугольников
77. Решение нелинейного уравнения методом касательных
78. Методы корреляционного и регрессионного анализа в экономических исследованиях
79. Современные криптографические методы
80. Математические методы в организации транспортного процесса
81. Вычисление интегралов методом Монте-Карло
82. Построение решения задачи Гурса для телеграфного уравнения методом Римана
83. Методы и приемы решения задач
84. Приближенный метод решения интегралов. Метод прямоугольников (правых, средних, левых)
85. Методы обучения математике в 10 -11 класах
89. Метод прогонки решения систем с трехдиагональными матрицами коэффициентов
90. Решение задач на построение сечений в многогранниках методом следов
91. Новый метод «дополнительных краевых условий» Алексея Юрьевича Виноградова для краевых задач
92. Лазерные методы диагностики. Термография
94. Дополнительные методы обследования легочных больных. Основные синдромы при заболеваниях легких
95. Хламидиоз. Методы определения/диагностики
96. Предмет, метод, содержание cудебной медицины
97. Методы оценки кровопотери в акушерстве
98. Метод Фолля
99. Некоторые методы лечения переломов длинных трубчатых костей