Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 41
Текст из файла (страница 41)
подразд. 6.2, стр. 91. Оба эти варианта требуют многократногоприменения операции извлечения квадратного корня. Если в п. 3 алгоритмавычислять разложение Холесского без операции квадратного корня: либоΛ = S̄DS̄ T c S̄ = L̄, либо S̄ = Ū , то п.
4 заменится на последовательноерешение трех систем: S̄w = d ⇒ Dy = w ⇒ S̄ T x̄ = y.12.2 Формирование матрицы A12.2Формирование матрицы AИспользуйте следующие четыре варианта формирования матрицы A дляоценки скорости и точности двух методов решения переопределенных системлинейных алгебраических уравнений, как указано в пп. В и Г задания (см.Задание ниже в подразд. 12.3).Для n = 2 до 12 с шагом 5 выполнятьДля m = n + 1 до 26 с шагом 3 выполнятьДля i = 1 до m выполнятьДля j = 1 до n выполнять(i − 1)j,Вариант 1: aij = sinm1Вариант 2: aij =4 ,(i − 1)j1 + 66mВариант 3: aij = 1/(i + j) ,Вариант 4: aij = 100(RAN − 1/2) ,где RAN — равномерно распределенная в интервале [0, 1] случайная величина, получаемая независимо для каждого элемента aij матрицы A.12.3Задание на лабораторный проект № 8А.
Спроектировать и отладить подпрограмму решения несовместной системы Ax = z, A = A(m, n), m > n, rank(A) = n, в смысле наименьших квадратов при помощи заданного метода ортогонального приведения.Обосновать проект и дать набор инструкций для пользователей подпрограммы. Сделать подсчет операций (отдельно сложения, умножения, деления и извлечения квадратного корня) в зависимости от m и n, где m — числострок матрицы A, а n — число столбцов. Рекомендуется в качестве основывашего проекта использовать ту программу, которая была вами написанаи отлажена в рамках лабораторного проекта № 6 для решения совместнойсистемы уравнений Ax = f с квадратной матрицей A методом ортогонального приведения.
Для этого в указанной программе достаточно осуществитьнезначительные изменения.26512 Одновременное решение нормальных уравненийБ. Повторить п. А задания на основе метода нормальных уравненийA Ax̄ = AT z, которым удовлетворяет искомое решение x̄ в смысле наименьших квадратов, называемое нормальным псевдорешением несовместнойсистемы Ax ≈ z. Для этого применить вашу программу решения системыуравнений с симметричной положительно определенной матрицей методомквадратного корня (разложение Холесского) из лабораторной работы № 5.В. Спроектировать и провести вычислительный эксперимент для сравнения скорости выполнения двух программ по пп. А.
и Б. Использоватьчетыре различных варианта генерации n векторов длины m для формирования матрицы A (см. подразд. 12.2) при 2 ≤ n ≤ 12, n + 1 ≤ m ≤ 26.Результаты представить в виде таблиц и графиков, которые иллюстрируютповедение каждого метода на каждом варианте генерации матрицы A. Датьобобщенную (по вариантам матрицы) картину зависимости времени выполнения от значений параметров m и n матрицы. Проанализировать соотношение между фактическим временем выполнения и числом операций, рассчитанным по пп. А и Б. Правые части уравнений формировать, как указанов следующем пункте задания.Г.
Подобно п. В, сравнить точность нахождения нормального псевдорешения переопределенной системы линейных уравнений для методов из пп. Аи Б. Для этого также четырьмя способами сгенерировать матрицу A (см.подразд. 12.2), выбрать (принудительно задать) точное нормальное псевдорешение x∗ и образовать вектор z ∗ = Ax∗. К элементам этого векторадобавить случайные числа vi , чтобы образовать правые части zi = zi∗ + avi ,i = 1, 2, . . . , m. Написать подпрограмму генерации псевдослучайных чиселvi так, чтобы каждое vi, имело стандартное нормальное распределение (снулевым средним значением и единичной дисперсией). При этом любые случайные величины vi, vj (i 6= j) должны моделироваться как попарно независимые. Предусмотреть множитель-переключатель a, чтобы по желаниювключать или отключать добавление случайных чисел vi , или же регулировать их уровень.В качестве точного нормального псевдорешения взять вектор x∗ == [1, 2, .
. . , m]T . Для оценки точности оценивания использовать норму вектораTkxk∞ = max(|xi|).iПри использовании программы, где выполняется ортогональное приведение QA = B, для проверки правильности метода убедиться в справедливо26612.3 Задание на лабораторный проект № 8сти равенства AT A − B T B = 0. Для этого использовать норму матрицыnXkAk∞ = max|aij | .ij=1Д. Представить обобщенную аттестацию двух подпрограмм и соответствующих методов, основанную на проведенных наблюдениях. Обсудитьлюбые сравнительные достоинства и недостатки, поддающиеся количественной оценке, и предложить план дальнейших вычислительных экспериментов, которые могли бы помочь уточнить различия между рассмотреннымивыше методами решения переопределенных систем уравнений.Е. Решить следующую прикладную задачу [82].
Для i = 1, 2, . . . , m (mкратно четырем) имеемyi = x1wi + x2wi−1, wi = sin(2πi/m),di = 2 cos(2πi/m).Найти оптимальное значение x̄ = (x̄1, x̄2)T вектора коэффициентов x == (x1, x2)T , доставляющее минимум средней квадратической ошибкеm1 X(yi − di )2.J(x) =m i=1Решение выполнить двумя способами: аналитически и численно. Аналитическое решение должно включать:1) эквивалентную постановку задачи в виде переопределенной системыAx ≈ z ,2) решение для нее нормальных уравнений, дающееhiTx̄ = 2 ctg(2π/m)− cosec(2π/m) ,3) представление критерия качества для общего случая в видеJ(x) = Jmin + (x − x̄)T Λ(x − x̄) ,где Λ = AT A — информационная матрица, x̄ = (AT A)−1AT z — нормальное псевдорешение ,4) доказательство того, что в данном конкретном случаеJmin = min(J(x)) = J(x̄) = 0 ,x26712 Одновременное решение нормальных уравнений5) вычисление собственных значений (λ1, λ2 ) матрицы Λ, дающееii1h1hλ1 = 1 − cos(2π/m) , λ2 = 1 + cos(2π/m) ,226) вычисление соответствующих собственных векторов (v1, v2) матрицы Λ ,7) представление критерия качества для общего случая в видеJ(x) = Jmin + eT QΛ̄QT e ,где e = x− x̄ — отклонение x от оптимального значения x̄, Q — матрицаортонормированных собственных векторов матрицы Λ, диагональнаяматрица Λ̄ = diag [λ1, λ2 ] составлена из собственных значений матрицыΛ, так что Λ = QΛ̄Q−1 = QΛ̄QT .Изобразить на экране в системе координат [x1, x2] = xT линии постоянныхуровней критерия J(x) = const для шести значений const = {1, 2, 3, 4, 5, 6}в окрестности точки минимума критерия для одного из значений m == 4, 8, 12, 16, 20, 24, 28 или 32 (по выбору).
Объяснить геометрический смыслматриц Q и Λ̄ в последнем представлении критерия.Численное решение должно включать вычисление решения x̄ с помощьюдвух методов (по пп. А и Б) и сравнительную оценку точности двух решенийдля нормы вектора kx̄k∞ (в зависимости от m = 4, 8, 12, 16, 20, 24, 28, 32).Эту зависимость необходимо представить таблицей и графиком.12.4Варианты задания на лабораторный проект № 8По теме «Одновременное решение нормальных уравнений» студентампредлагается выполнение лабораторной работы — проекта № 8.Задание на этот проект содержит 28 вариантов, которые аналогичнывариантам, приведенным в табл.
7.2 (см. стр. 139) для проекта № 6. Всеварианты различаются по следующим признакам:•четыре варианта заполнения треугольной матрицы R;•три вида ортогональных преобразований:1) отражения Хаусхолдера,2) вращения Гивенса,3) ортогонализация Грама–Шмидта,26812.4 Варианты задания на лабораторный проект № 8Таблица 12.1. Варианты задания на лабораторный проект № 8Вариантзаполненияматрицы R00a——c—d—e—b•ОтраженияХаусхолдераВращенияГивенсаОртогонализацияГрама-Шмидтаababcde, Rne12345670 , Rnw891011121314, Rse151617181920210 , Rsw22232425262728столбцово-ориентированный алгоритм;строчно-ориентированный алгоритм;классическая схема;модифицированая схема;модифицированая схема с выбором ведущего вектора.две разновидности алгоритма ортогонализации по методу Хаусхолдераи по методу Гивенса:1) столбцово-ориентированный алгоритм,2) строчно-ориентированный алгоритм,•три разновидности ортогонализации по методу Грпма–Шмидта:1) классическая схема,2) модифицированная схема,3) модифицированная схема с выбором ведузего вектора.Если нет других указаний преподавателя, выбирайте ваш вариант втабл.
12.1 по вашему номеру в журнале студенческой группы.26913Устойчивые алгоритмы фильтрации13.1Фильтрация Калмана в историческом аспектеВскоре после открытия Калманом своего ставшего знаменитым новогоподхода к задачам фильтрации и предсказания [101] выяснилось, что этоизящное решение, которое теперь принято называть «обыкновенным» илистандартным фильтром Калмана (the conventional Kalman filter, CKF),работает хорошо лишь в исключительных — так называемых хорошо обусловленных задачах — и расходится в большинстве практических задач.Явление расходимости теоретического алгоритма CKF, детально исследованное 10 лет спустя [98], породило поиски альтернатив, алгебраически эквивалентных CKF, но в вычислениях значительно более устойчивых.В 1963 году Поттер нашел первое решение [125] в связи с разработкой американского лунохода (Lunar Excursion Module, LEM) для Программы Аполлон.
По природе, это квадратно-корневой алгоритм, названный квадратнокорневым фильтром Поттера, PSRF (Potter Square Root Filter). Будучиприспособлен лишь для ограниченных случаев (некоррелированность скалярных измерений и отсутствие шума в уравнении состояния), PSRF породил две ключевые идеи: (1) факторизация (разложение на множители)ковариационных матриц, чтобы устранить опасность потери положительнойопределенности, и (2) декорреляция и последующая скаляризация векторных измерений, чтобы устранить операцию вычисления обратной матрицыв алгоритме CKF.Любой квадратно-корневой алгоритм фильтрации численно более устойчив, чем CKF, так как число обусловленности квадратного корня из матрицы есть квадратный корень из числа обусловленности соответствующейматрицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
