ЧМ_Билеты. 1. Основные характеристики численных методов. Взаимосвязь характеристик
 Скачать 1.85 Mb.
|
|
Обобщенная регрессия Линейная регрессия предназначена для определения коэффициентов линейной функции y=ax+b, которая наилучшим образом приближает экспериментальные данные. Задача обобщенной линейной регрессии – ответить на следующий вопрос: какие значения должны принимать коэффициенты a 0 , a 1 , ..., a N , чтобы функция F(x), являющаяся линейным сочетанием N+1 произвольной функции f 0 (x), f 1 (x), ..., f N (x) (то есть F(x)=a 0 f 0 (x)+a 1 f 1 (x)+...+a N f N (x)), проходила между экспериментальными точками так, чтобы сумма квадратов расстояний от точек и до кривой F(x) была минимальной? 31 Формулу для расчета обобщенной линейной регрессии: C 1 f 1 (x) + C 2 f 2 (x) +… + . . . , где f N (x) – любые функции пользователя, a C N – подлежащие определению коэффициенты 16. Задаваемая и фактическая ошибки при вычислении значения интеграла. Зависимость фактической ошибки от шага интегрирования и задаваемой ошибки. Затраты машинного времени. Краткие сведения Для вычисления определенного интеграла используется формула Ньютона- Лейбница если первообразная ) (x F может быть найдена или не является слишком громоздкой: ). ( ) ( ) ( a F b F dx x f b a В противном случае вычисляют приближенное значение интеграла по квадратурной формуле b a n i i i x f A dx x f 1 ) ( ) ( содержащей 1 2 n параметров ( n абсцисс i x , n коэффициентов i A и число узлов), которые нужно выбрать так чтобы формула давала достаточно малую погрешность для широкого класса функций ) (x f . Очевидно чем больше n , тем выше точность Указанному требованию удовлетворяют квадратурные формулы Ньютона-Котеса и квадратурная формула Гаусса Пусть шаг интегрирования h = const, — вычисленное с шагом h приближение к I. Если, далее вычислено также приближенное значение с шагом то в качестве приближенной оценки погрешности последнего вычисленного значения можно рассматривать величину 32 На практике, при необходимости вычислить результат с требуемой точностью вычисления повторяются с последовательно уменьшающимся (вдвое) шагом до тех пор, пока не выполнится условие Рис.7.1 – алгоритм получения зависимости фактической ошибки интегрирования функции по формуле прямоугольников от шага интегрирования начало b a, ) ( ) ( a F b F s 20 ) 1 ( 1 k 0 , y k a b h h x b x h a x , , 2 / ) (x f y x h y * h y s , k конец 33 17. Алгоритмы формирования матриц (верхней и нижней треугольных, неособенной и особенной). Рис.7.7 – адаптивный алгоритм получения зависимостей фактической ошибки и временных затрат при интегрировании функции по формуле прямоугольников от задаваемой ошибки начало b a, ) ( ) ( a F b F s 10 * ; 011 0 ; 10 5 0 , ys a b h h x b x t y h a x ; ; 0 , 0 , 2 / t x f y ), ( x h y * t y s , , конец y ys y 2 / h h y ys да 34 Верхняя треугольная матрица (или верхнетреугольная матрица) — квадратная матрица , у которой все элементы ниже главной диагонали равны нулю: Нижняя треугольная матрица (или нижнетреугольная матрица) -квадратная матрица , у которой все элементы выше главной диагонали равны нулю: Невырожденная матрица (иначе неособенная матрица) ― квадратная матрица, определитель которой отличен от нуля. В противном случае матрица называется вырожденной. Для квадратной матрицы M над полем невырожденность эквивалентна каждому из следующих условий: • M обратима, то есть существует обратная матрица; • строки (столбцы) матрицы M линейно независимы; • ранг матрицы равен её размерности. Вы́рожденная ма́трица (синонимы: сингуля́рная ма́трица, осо́бая ма́трица, осо́бенная ма́трица) — квадратная матрица A определитель которой равен нулю. 35 начало ) 1 )( 1 ( 0 ) 1 )( 1 ( 0 n j n i j i () rand l ij 0 ij l () rand u ij 0 ij u 0 () ij ij u rand l j i () 0 rand u l ij ij i j, ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i l ij да да ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i u ij конец 1 n n u l ) 1 )( 1 ( 0 n i ii n ii n u u l l * , * i n n u l , матрицы й треугольно нижней вывод матрицы й треугольно верхней вывод лей определите вывод да да Рис.3.1 – алгоритм формирования нижней и верхней треугольных матриц с ненулевыми элементами на главных диагоналях 36 18. Разложение неособенной матрицы в произведение треугольных матриц. Алгоритм. Характеристики разложения. Рис.3.2 – алгоритм формирования неособенной квадратной матрицы как произведение нижней и верхней треугольных матриц с ненулевыми элементами на главных диагоналях начало ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i l ij ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i u ij 0 ij a ) 1 )( 1 ( 0 n i ) 1 )( 1 ( 0 n j ) 1 )( 1 ( 0 n k kj ik ij u l a * i j k , , ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i a ij конец матрицы й треугольно верхней ввод матрицы квадратной й неособенно вывод матрицы й треугольно нижней ввод 37 Выше было указано, что всякую квадратную матрицу A имеющую отличные от нуля главные диагональные миноры ; 0 11 1 a ; 0 22 21 12 11 2 a a a a ….; , 0 A n можно представить в виде произведения двух треугольных матриц (верхней и нижней) причем это разложение будет единственным если зафиксировать диагональные элементы одной из матриц (например принять их равными 1). Следовательно, U L A * , где L и U – нижняя и верхняя треугольные матрицы соответственно. Для разработки алгоритма необходимо получить формулы, позволяющие вычислять элементы нижней и верхней треугольных матриц по известным значениям элементов исходной матрицы A. При 4 n из произведения матриц A U L * имеем: , 43 33 43 23 42 13 41 a u l u l u l , 33 33 33 23 32 13 31 a u l u l u l 34 34 33 24 32 14 31 a u l u l u l Распространив эти формулы на общий случай ( n - произвольное), получим формулы для вычисления элементов матрицы L : ..., , 2 , 1 , 1 n i l ii 1 1 1 ..., , 2 , 1 ; ..., , 3 , 2 , / ) ( j k jj kj ik ij ij i j n i u u l a l и формулы для вычисления элементов матрицы U : 1 1 ..., , 2 , 1 , j k kj jk jj jj n j u l a u 1 1 ..., , 1 ; 1 ..., , 2 , 1 , i k kj ik ij ij n i j n i u l a u Полученные формулы позволяют построить алгоритм разложения неособенной квадратной матрицы в произведение двух треугольных матриц: верхней и нижней с 38 единичной главной диагональю (рис.3.3). Рис.3.3 – алгоритм разложения неособенной квадратной матрицы в произведение двух треугольных матриц: верхней и нижней с единичной главной диагональю начало ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i a ij ) 1 )( 1 ( 0 n i 1 ii l ) 1 )( 1 ( 0 n j j i 0 , 0 b u ij ) 1 )( 1 ( 0 j k kj ik u l b * да k jj ij ij u b a l j i 0 c 0 , 0 d l ij да ) 1 )( 1 ( 0 j k kj jk u l c * k c a u jj jj ) 1 )( 1 ( 0 i k kj ik u l d * k d a u ij ij i j, ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i l ij ) 1 )( 1 ( 0 ), 1 )( 1 ( 0 , n j n i u ij конец матрицы квадратной й неособенно исходной ввод матрицы й треугольно нижней вывод матрицы й треугольно верхней вывод 39 19. Методы обращения матриц. Характеристики обращения. Методы обращения матриц Могут быть обращены только неособенные квадратные матрицы Метод окаймления (деления на клетки) Исходную матрицу M размера n n разобьем на четыре клетки d c b a M где d c b a , , , – подматрицы размеров q q p q q p p p , , , Примем что матрица 1 M существует и может быть разбита на клетки так же как и матрица M те D C B A M 1 где D C B A , , , – подматрицы размеров q q p q q p p p , , , Поскольку E MM 1 , то d c b a * D C B A = q p E E 0 0 или , 0 , 0 , q p E dD cB dC cA bD aB E bC aA Пусть подматрица d имеет обратную 1 d которая известна Тогда после небольших преобразований получим формулы которые могут быть последовательно решены относительно матриц D C B A , , , : , , , 1 1 1 1 1 1 cB d d D cA d C Abd B c bd a A (*) Вычисление обратной матрицы реализуется с помощью метода окаймления Суть его заключается в следующем Пусть дана матрица nn n n m m m m M 1 1 11 Образуем 11 1 m M ; 22 21 12 1 2 m m m M M ; 33 32 31 23 13 2 3 m m m m m M M и тд 40 Каждая следующая матрица получена из предыдущей при помощи окаймления Обратная к первой из этих матриц находится непосредственно: 11 1 1 1 m M Зная 1 1 M и применив к 2 M схему вычислений (*) можно получить 1 2 M а затем при помощи 1 2 M аналогично получить 1 3 M и тд Процесс заканчивается матрицей 1 n M тк 1 1 M M n . Обращение можно начать и с правого нижнего угла матрицы M . Метод Ершова (метод пополнения) На основе исходной матрицы A и единичной матрицыE строится последовательность матриц , ) 0 ( , ) ( , ' ) ( ....., , ) 1 ( , ' ) 1 ( , ) 0 ( E A A где n A n A A A A , 0 , 1 , ) 1 ( ' ) ( m ij a m ij a если если если m i m i m i , и и ; , j i j i ) 1 ( 1 / ) 1 ( * ' ) ( ' ) ( ) ( m mm a m mj a m im a m ij a m ij a ; n m j i ..., , 2 , 1 , , Матрица ) 1 ( ) ( A A n Матрицы ' ) ( ' ) 2 ( ' ) 1 ( ........, , , n A A A являются вспомогательными Метод Фаддеева Напомним что следом (spur) матрицы A называется сумма ее элементов на главной диагонали: i ii a SpA n i ..., , 2 , 1 Вычисление обратной матрицы 1 A порядка n производится по следующим формулам: 1 , 1 , ; , 1 1 , ; , 2 1 , ; , , 1 1 1 1 1 1 1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 1 1 n n n n n n n n n n n n n B p A SpA n p AB A E p A B SpA n p AB A E p A B SpA p AB A E p A B SpA p A A 41 20. Прямые методы решения СЛАУ. Алгоритм метода Гаусса с частичным выбором ведущего коэффициента по столбцу. Ошибки и затраты машинного времени. Метод Гаусса Методом Гаусса называют точный метод решения невырожденной системы линейных уравнений состоящий в том что последовательным исключением неизвестных систему i n j j ij b x a 1 n i ..., , 2 , 1 приводят к эквивалентной системе с верхней треугольной матрицей , , , , 2 2 2 1 1 2 12 1 n n n n n n d x d x c x d x c x c x решение которой находят по рекуррентным формулам n i k k ik i i x c d x 1 n n d x 1 ...., , 2 , 1 n n i Существует много вариантов этого метода Рассмотрим схему единственного деления Она эффективна когда максимальные по модулю коэффициенты уравнений находятся на главной диагонали матрицы Это положительно определенные матрицы и матрицы обладающие свойством диагонального преобладания: n i a a n i j j ii ij ..., , 2 , 1 ,| | | | , 1 Пусть исходная система имеет вид ...., , 1 1 1 1 1 11 n n nn n n n b x a x a b x a x a (1) Предположим что 0 11 a и разделим обе части первого уравнения системы на 11 a В результате получим 42 ) 1 ( 1 ) 1 ( 1 2 ) 1 ( 12 1 b x a x a x n n (2) где 11 1 ) 1 ( 1 / a a a j j n j ,...., 3 , 2 11 1 ) 1 ( 1 / a b b С помощью уравнения (2) исключим во всех уравнениях системы (1) начиная со второго слагаемые содержащие 1 x Для этого умножаем обе части уравнения (2) последовательно на 1 31 21 ..., , , n a a a и вычитаем соответственно из второго третьего n -го уравнения системы (1) В результате получаем систему порядок которой на единицу меньше порядка исходной системы: , ....., , ) 1 ( ) 1 ( 2 ) 1 ( 2 ) 1 ( 2 ) 1 ( 2 2 ) 1 ( 22 n n nn n n n b x a x a b x a x a где ) 1 ( 1 1 ) 1 ( j i ij ij a a a a n j i ....., , 3 , 2 , ) 1 ( 1 1 ) 1 ( b a b b i i i n i ..., , 3 , 2 Аналогично преобразуем полученную систему В результате n - кратного повторения этого преобразования получим систему с треугольной матрицей: , 2 2 3 23 2 1 1 3 13 2 12 1 ..., , , n n n n n n d x d x c x c x d x c x c x c x (3) которая эквивалентна системе (1) и легко решается Найденное из последнего уравнения n x подставляют в предпоследнее уравнение и находят 1 n x затем 2 n x и тд до 1 x которое находят из первого уравнения системы когда уже известны 2 2 1 ..., , , , x x x x n n n Таким образом метод Гаусса содержит прямой ход на котором исходную систему преобразуют к треугольному виду и обратный ход на котором решают треугольную систему (3) эквивалентную исходной На рис.4.1 и 4.2 представлены алгоритмы прямого хода и обратного хода при решении системы. 43 Рис.4.1 – прямой ход алгоритма решения системы линейных алгебраических уравнений методом Гаусса по схеме с частичным выбором ведущего коэффициента по столбцу начало n j n i a n ij ) 1 ( 0 ), 1 )( 1 ( 0 , , уравнений ских алгебраиче линейных системы частей правых и тов коэффициен матрицы ввод ) 2 )( 1 ( 0 n i i m ) 1 )( 1 )( 1 ( n i k mi ki a a k m нет k n i j ) 1 ( z a a a a z mj mj ij ij , , j ii a c n i j ) 1 ( c a a ij ij / j ) 1 )( 1 )( 1 ( n i k ki a b n i l ) 1 ( il kl kl a b a a * i k l , , 1 1 2 ) 1 ( строки ю n по той i с столбца го i части в фициента коэф модулю по мального макси поиск местами меняются строка я i и м эффициенто ко модулю по макс с строка 44 Другие прямые методы: Жордана-Гаусса, ортогональных строк, с ленточными коэффициентами, метод Холецкого, метод квадратного корня, LUразложения, метод прогонки, метод вращения. 21. Итерационные методы решения СЛАУ. Алгоритм метода Гаусса- Зейделя. Для систем средней размерности чаще используют прямые методы Итерационные методы применяют для решения задач большой размерности когда использование прямых затруднено из-за необходимости выполнения чрезмерно большого числа арифметических операций Большие системы уравнений как правило Рис.4.2 – обратный ход алгоритма решения системы линейных алгебраических уравнений методом Гаусса по схеме с частичным 2 1 , 1 , 1 1 / n n n n n a a x 0 ) 1 )( 2 ( n k 0 s ) 1 )( 1 )( 1 ( n k j j kj x a s * j s a x kn k k ) 1 )( 1 ( 0 , n i x i системы решения вывод конец 45 бывают разреженными Методы исключения приводят к тому что большое число нулевых элементов превращаются в ненулевые и матрица теряет свойство разреженности А в ходе итерационного процесса матрица не меняется и остается разреженной Большая эффективность итерационных методов по сравнению с прямыми методами связана с возможностью существенного использования разреженных матриц. Методы: простой итерации(Якоби), метод релаксации Метод Зейделя (метод Гаусса-Зейделя процесс Либмана метод последовательных замещений) На k+1-й итерации компоненты приближения ) 1 ( k x вычисляются по формулам: , , , 1 ( 1 1 , ) 1 ( 3 3 ) 1 ( 2 2 ) 1 ( 1 1 ) 1 ( 3 ) ( 3 ) ( 1 1 , 3 ) 1 ( 2 32 ) 1 ( 1 31 ) 1 ( 3 2 ) ( 2 ) ( 1 1 , 2 ) ( 3 23 ) 1 ( 1 21 ) 1 ( 2 1 ) ( 1 ) ( 1 1 , 1 ) ( 3 13 ) ( 2 12 ) 1 ( 1 n k n n n k n k n k n k n k n n k n n k k k k n n k n n k k k k n n k n n k k k c x b x b x b x b x c x b x b x b x b x c x b x b x b x b x c x b x b x b x b x Метод Якоби ориентирован на системы с матрицами близкими к диагональным а метод Зейделя – на системы с матрицами близкими к нижним треугольным Алгоритм метода Зейделя представлен на рис.4.3. 46 Рис.4.3 – алгоритм итерационного метода Гаусса-Зейделя решения систем линейных алгебраических уравнений начало n j n i a n ij ) 1 ( 0 ), 1 )( 1 ( 0 , , ) 1 )( 1 ( 0 , , n i x i ) 1 )( 1 ( 0 n i 0 s ) 1 )( 1 ( 0 n j j ij x a s * j z x z x z t x a s a z i i i i ii in , / ) ( , / ) ( i ) 1 )( 1 ( 0 n i i t да i ) 1 )( 1 ( 0 , n i x i конец уравнений браических алге линейных системы частей правых и ентов коэффици матрицы ввод системы решения ого приближенн и ошибки ввод ошибок текущих массив t системы решения вывод 47 22. Сравнение прямых и итерационных методов решения СЛАУ. Рекомендации при вычислении матричных выражений. Итерационные методы применяют для решения задач большой размерности когда использование прямых затруднено из-за необходимости выполнения чрезмерно большого числа арифметических операций Большие системы уравнений как правило бывают разреженными Методы исключения приводят к тому что большое число нулевых элементов превращаются в ненулевые и матрица теряет свойство разреженности А в ходе итерационного процесса матрица не меняется и остается разреженной Большая эффективность итерационных методов по сравнению с прямыми методами связана с возможностью существенного использования разреженных матриц В матричных выражениях следует избегать вычисления обратных матриц, т.к. на это требуется большее время, чем на остальные вычисления. Например, требуется вычислить W WD CA B V 1 1 1 при известных W D C B A , , , , Ошибочно вычислять сначала 1 1 1 , , D A B , а затем – по формуле. Нужно вычислять с меньшими затратами машинного времени, в следующей последовательности. Решая систему W Dx , находят W D x 1 , затем - Wx y Решая систему y Az , находят y A z 1 , затем - Cz u Решая систему u BV , находят u B V 1 23. Постановка задачи аппроксимации (регрессии). Выбор критерия. |