УМК (1013374), страница 15
Текст из файла (страница 15)
Заметим, что при aii( k ) = a (jjk ) получается ϕ( k ) = .4В процессе итераций сумма квадратов всех недиагональных элементов σ( A (k ) )где 2ϕ(k ) ≤при возрастании k уменьшается, так что σ( A (k +1) ) < σ( A (k ) ) . Элементы aij(k ) , приведенные к нулю на k -й итерации, на последующей итерации немного возрастают. Приk → ∞ получается монотонно убывающая ограниченная снизу нулем последовательность σ( A (1) ) > σ( A (2) ) > " > σ( A (k ) ) " . Поэтому σ( A (k ) ) → 0 при k → ∞ .
Это и озна0 ⎞⎛ λ1⎜⎟(k )чает сходимость метода. При этом A%→Λ=⎜⎟.⎜0λ n ⎟⎠⎝Методика решения задачиШаг 1. Положить k = 0, A (0) = A и задать ε > 0.86Шаг 2. Выделить в верхней треугольной наддиагональной части матрицы A (k )максимальный по модулю элемент aij(k ) , i < j .Если aij(k ) ≤ ε для всех i ≠ j , процесс завершить. Собственные значения опреде-()ляются по формуле λ i A (k ) = aii(k ) , i = 1, n.Собственные векторы X i находятся как i -е столбцы матрицы, получающейся врезультате перемножения:()ν k = H (0) H (1) H (2) " H (k −1) = X 1 , X 2 , X 3 ,..., X n .Если aij(k ) > ε , процесс продолжается.Шаг 3. Найти угол поворота по формуле(k )(k )ϕ2aij1= arctg2aii( k ) − a (jjk )(при aii( k ) = a (jjk ) получается ϕ( k ) =π).4Шаг 4.
Составить матрицу вращения H (k ) .Шаг 5. Вычислить очередное приближение(A (k +1) = H (k ))TA (k ) H (k ) .Положить k = k + 1 и перейти к п.2.З а м е ч а н и я.1. Контроль правильности выполнения действий на каждой итерации осуществляется путем проверки сохранения следа преобразуемой матрицы.2. При n = 2 для решения задачи требуется одна итерация.⎛ 2 1⎞⎟⎟ методом вращений найти собственные значеПример 2. Для матрицы A = ⎜⎜⎝1 3⎠ния и собственные векторы.⎛ 2 1⎞⎟⎟ , ε = 10 −10. 1.
Положим k = 0, A (0) = A = ⎜⎜⎝ 1 3⎠2 0. Выше главной диагонали имеется только один элемент aij = a12 = 1.30. Находим угол поворота матрицы, используя в расчетах 11 цифр после запятойв соответствии с заданной точностью:87tg 2ϕ(0) =2aijaii − a jj=2= −2;2−3sin ϕ(0) = − 0,52573111212 ;cos ϕ(0) = 0,85065080835.4 0. Сформируем матрицу вращения:⎛ cos ϕ (0)H (0) = ⎜⎜(0 )⎝ sin ϕ− sin ϕ (0) ⎞⎟ ⎛ 0,8506508083 5 0,5257311121 2 ⎞⎟⎟.= ⎜⎜cos ϕ (0) ⎟⎠ ⎝ − 0,5257311121 2 0,8506508083 5 ⎠50. Выполним первую итерацию:(A (1) = H (0 ))TA (0 ) H ( 0 ) =⎛ 0,8506508083 5 − 0,5257311121 2 ⎞ ⎛ 2 1 ⎞ ⎛ 0,8506508083 5 0,5257311121 2 ⎞⎟⎟ ⎜⎜⎟⎟ ⎜⎜⎟⎟ == ⎜⎜⎝ 0,5257311121 2 0,8506508083 5 ⎠ ⎝ 1 3 ⎠ ⎝ − 0,5257311121 2 0,8506508083 5 ⎠⎛1,3819660112 5= ⎜⎜−12⎝ − 4,0458747463 4 ⋅ 10Очевидно,22i =1i =1следматрицыс− 4,0462078132 5 ⋅ 10 −12 ⎞⎟⎟.3,6180339887 4⎠заданнойточностьюсохраняется,т.е.∑ aii(1) = ∑ aii(0) = 5 .
Положим k = 1 и перейдем к п.2.a1221.Максимальныйпомодулюнаддиагональныйэлемент−12−10= 4,04620781325 ⋅ 10< ε = 10 . Для решения задачи (подчеркнем, что n = 2 ) спринятой точностью потребовалась одна итерация, полученную матрицу можно считатьдиагональной. Найдены следующие собственные значения и собственные векторы:λ1 = 1,38196601125;λ 2 = 3,61803398874;⎛ 0,85065080835 ⎞⎟⎟;X 1 = ⎜⎜⎝ − 0,52573111212 ⎠⎛ 0,52573111212 ⎞⎟⎟ . X 2 = ⎜⎜⎝ 0,85065080835 ⎠88Лекция 113. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИПусть дано нелинейное уравнениеf (x ) = 0 ,(3.1)где f (x ) – функция, определенная и непрерывная на некотором промежутке. В некоторых случаях на функцию f (x ) могут быть наложены дополнительные ограничения, например, непрерывность первой и второй производных, что специально оговаривается.Функция f (x ) может быть задана в виде алгебраического многочлена или трансцендентной функции (тогда ей соответствует алгебраическое или трансцендентное уравнение).Требуется найти корни уравнения, т.е.
числа x ∗1 , x ∗ 2 , … , которые путем подстановки превращают уравнение в верное числовое равенство. Числа x ∗1 , x ∗ 2 , … называютсятакже нулями функции f (x ) .На практике часто бывает выгодно уравнение (3.1) заменить равносильным емууравнением (уравнения равносильны, если имеют одинаковые корни):f1 ( x ) − f 2 ( x ) = 0 ,(3.2)где функции f1 ( x ) , f 2 ( x ) – более простые, чем функция f (x ) . Тогда при задании уравнения в виде (3.1) нулями функции f (x ) являются точки пересечения f (x ) с осью Ox(рис.1,а), а при задании в виде (3.2) – абсциссы точек пересечения функций f1 ( x ) иf 2 ( x ) ( рис.
1,б).yyy = f1 ( x )y = f (x )y = f2 (x )0x ∗1x∗2x ∗3x∗4x ∗5аx0бРис. 189a1b1x∗1a2b2x∗2 xЧисло x ∗ есть корень уравнения (3.1) кратности k , если при x = x ∗ вместе сфункцией f (x ) обращаются в нуль ее производные до (k − 1) -го порядка включительно,т.е. f ( x ∗ ) = f ′( x ∗ ) = … = f (k −1) ( x ∗ ) = 0 , а f (k ) ( x ∗ ) ≠ 0 .
Корень кратности k = 1 называется простым. На рис. 1,а простыми корнями являются x ∗1 ,x ∗ 2 ,x ∗3 , а корни x ∗ 4 ,x ∗5 –кратные.З а м е ч а н и я.1. Если f ( x ) = an x n + an −1 x n −1 + + a0 = Pn ( x ) – алгебраический многочлен, тоуравнение (3.1) называется также алгебраическим n -й степени:Pn ( x ) ≡ an x n + an −1 x n −1 ++ a0 = 0 ,(3.3)где an , … a0 – действительные числа, коэффициенты уравнения.2. Алгебраическое уравнение n -й степени имеет ровно n корней, действительныхили комплексных, при условии, что каждый корень считается столько раз, какова егократность.3. Если функция f ( x ) , определяющая уравнение f ( x ) = 0 , на концах отрезка[ai , bi ] принимает значения разных знаков, т.е.
f (ai ) ⋅ f (bi ) < 0 , то на этом отрезке содержится по крайней мере один корень уравнения. Если же f ( x ) непрерывна и дифференцируема и ее первая производная сохраняет знак внутри отрезка [ai , bi ]⎞⎛⎜ sign f ′( x ) = const ⎟ , то на [ai , bi ] находится только один корень x ∗i уравнения.⎟⎜ [a ,b ]⎠⎝ i iЭтапы решения нелинейных уравненийПервый этап. Находятся отрезки [ai , bi ] , внутри каждого из которых содержитсяодин простой или кратный корень ( x ∗i ∈ [ai , bi ] ) (см.
рис.1). Этот этап называется процедурой отделения корней. По сути, на нем осуществляется грубое нахождение корней x ∗i .Второй этап. Грубое значение каждого корня x ∗i уточняется до заданной точности одним из численных методов, в которых реализуются последовательные приближения.Отделение корнейДля отделения действительных корней полезно определять заранее число корней,а также верхнюю и нижнюю границы их расположения.В вычислительной практике обычно используются следующие способы отделениякорней:1) средствами машинной графики: функция f ( x ) представляется на дисплее иприближенно определяются отрезки, которым принадлежат точки x ∗i ;2) средствами математического анализа с помощью исследования функций и построения графиков (см. рис.
1,а);3) формированием простых функций f1 ( x ) и f 2 ( x ) таких, что получается равносильное уравнение в виде (3.2), и дальнейшим построением графиков этих функций (см.рис. 1,б).90А. МЕТОД ПРОСТЫХ ИТЕРАЦИЙПусть известно, что кореньG = {a ≤ x ≤ b}.уравненияx∗f (x ) = 0лежит на отрезкеМетодика решения задачиШаг 1. Уравнение f ( x ) = 0 равносильным преобразованием привести к видуx = ϕ( x ) . Это преобразование может быть осуществлено различными путями, но длясходимости нужно обеспечить выполнение условия ϕ′( x ) ≤ χ < 1 ( χ – некоторая константа). При этом задача сводится к нахождению абсциссы точки пересечения прямойy = x и кривой y = ϕ( x ) (рис.
2).yy=xy = ϕ( x )0x∗xРис. 2Шаг 2. Задать начальное приближение x ( 0 ) ∈ [a, b ] и малое положительное числоε . Положить k = 0 .Шаг 3. Вычислить следующее приближение:x ( k +1) = ϕ( x ( k ) ) .Шаг 4. Еслиx ( k +1) − x ( k ) ≤ ε , итерации завершаются и x ∗ ≅ x (k +1) . Еслиx ( k +1) − x ( k ) > ε , положить k = k + 1 и перейти к п.3.Теорема (о достаточном условии сходимости метода простых итераций).Пусть выполнены условия:1. Функция ϕ( x ) имеет производные для всех x ∈ G .2. Существует число χ (0 ≤ χ < 1, χ = const) , такое, что ϕ′(x ) ≤ χ для всехx ∈G .Тогда последовательность x (0 ) , x (1) , …, x (k +1) , … , определяемая на основе итера-ционного процесса, сходится к решению x ∗ , т.е. x (k ) → x ∗ при k → ∞ .91Геометрическая интерпретация процесса сходимости и расходимости в зависимости от выполнения или невыполнения достаточного условия сходимости представлена нарис.
3. Из рис. 3 видно, что при 0 < ϕ′(x ) < 1 и при − 1 < ϕ′(x ) < 0 (см. рис. 3, а, б) итерационные последовательности x (0 ) , x (1) , x ( 2) , … сходятся к x ∗ . Причем в первом случаереализуется односторонняя (монотонная) сходимость, а во втором – двусторонняя (немонотонная). При ϕ′( x ) > 1 (см.
рис. 3, в, г) процесс расходится, несмотря на то, что точкаx ( 0 ) очень близка к x ∗ .y0 < ϕ′( x ) < 1yy=xy=xϕ( x (0) )y = ϕ( x )ϕ( x (1) )− 1 < ϕ′( x ) < 0ϕ( x (1) )ϕ(x(0) )y = ϕ( x )x∗x (1)0 x (0 )x ( 2)x∗0 x (0 )xаyx ( 2)xx (1)бyϕ′( x ) > 1ϕ′( x ) < −1y = ϕ( x )y = ϕ( x )y=xy=xx ( 2)x∗0x (0) x (1) x (2)0xвx (1) x (0)гРис. 392xСпособы преобразования уравненияПреобразование уравнения f (x ) = 0 к равносильному виду x = ϕ(x ) может бытьвыполнено неоднозначно.1. Можно заменить уравнение f (x ) = 0 на равносильное x = x + c f (x ) , гдеc = const ≠ 0 . Тогда, принимая правую часть этого уравнения за ϕ( x ) и раскрываяϕ′( x ) = 1 + c f ′( x ) < 1 , получаем условие− 2 < c f ′(x ) < 0 .При этом надо стремиться получить такую постоянную c , которая бы больше отличаласьот нуля, и тогда будет реализовываться более быстрая сходимость.2.
Уравнение f ( x ) = 0 заменяется равносильным:x=x∓f (x )≡ ϕ( x ) при x ∈ G ,max f ′( x )где знак в правой части выбирается из условия ϕ′( x ) < 1 .3. Можно выразить x из уравнения f ( x ) = 0 так, чтобы для полученного уравнения x = ϕ( x ) выполнялось условие сходимости ϕ′( x ) < 1 в окрестности искомого корня.Б. МЕТОД НЬЮТОНАМетод Ньютона (метод касательных) является одним из наиболее популярныхчисленных методов. Он реализуется по формуле:x ( k +1) = x (k ) −f ( x (k ) ), k = 0,1, 2,...f ′( x ( k ) )yBf ( x (0 ) )y = f (x )a0Cx∗αAx ( 2)Рис. 493x (1)bx (0 )xВ точке x (0) строится касательная к графику функции.
Следующей точкой x (1) являетсяточка пересечения касательной с осью абсцисс. Далее процесс продолжается аналогично.Теорема (о достаточных условиях сходимости метода Ньютона).Пусть выполняются следующие условия:1. Функция f ( x ) определена и дважды дифференцируема на [a, b ] .2. Отрезку [a, b ] принадлежит только один простой корень x ∗ , так чтоf (a ) ⋅ f (b ) < 0 .3. Производные f ′( x ), f ′′( x ) на [a, b ] сохраняют знак, и f ′( x ) ≠ 0 .4. Начальное приближение x (0 ) удовлетворяет неравенствуf ( x (0) ) ⋅ f ′′( x (0) ) > 0 (знаки функций f ( x ) и f ′′(x ) в точке x ( 0 ) совпадают).Тогда с помощью метода Ньютона можно вычислить корень уравнения f ( x ) = 0с любой точностью.В. МОДИФИКАЦИИ МЕТОДА НЬЮТОНАВ1.
Упрощенный метод Ньютона. Вместо формулы метода Ньютона используетсяx(k +1)=x(k )−( ),f ′(x )f x (k )(0 )k = 0,1,...Отличие от метода Ньютона заключается в том, что производная функции f (x ) подсчитывается только в точке начального приближения, а на последующих итерациях не уточняется. Процесс последовательных приближений отражен на рис. 5. Первая итерациясовпадает с первой итерацией метода Ньютона. На последующих итерациях соответствующие отрезки параллельны касательной, проведенной в начальной точке.yy = f (x )0(1)x ( 2) xx∗Рис. 594x (0 )xВ2. Метод Ньютона–Бройдена. Этот метод позволяет увеличить скорость сходимости последовательных приближений благодаря использованию формулыf x (k )(k +1)(k )x=x− ck, k = 0,1,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
