Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 27
Текст из файла (страница 27)
11оэтому иногда целесообразно использовать смешанный алгоритм. Он состоит в том, что сначала применяется всегда сходящийся метод (например, метод деления отрезка пополам), а после некоторого числа итераций — быстро сходящийся метод Ньютона. $2. О РЕШЕНПП АЛГЕБРАПЧЕСКНХ УРАВНЕНПЙ 5. Метод простой итерации. Для использования этого метода исходное нелинейное уравнение записывается в виде (5.4) х = ~(х). Пусть известно начальное приближение корня х = с,. Подставляя это значение в правую часть уравнения (5.4), получаем новое приближение: с, = Дс,)'.
Далее, подставляя каждый раз повсе значение корня в (5.4), получаем последовательность значений с„+,—— 7'(с„)', и=1, 2, Итерационный процесс прекращается, если результаты двух последовательных итераций близки: ~ с„+, — с„~ ( е. Достаточным условием сходимости метода простой итерации является условие 1~'(с.)! ( 1. На рис. 27 представлена ~ блок-схема процесса решения ':- нелинейного уравнения (5.4) методом простой итерации. Здесь с — начальное приоли! жение корня, а в дальнейшем — результат предыдущей итерации, х — значение корня после каждой итерации. ' В данном алгоритме предполагалось, что итерацпонньрй1 процесс сходится.
Если такой уверенности нет, то неооходимо ограничить число итераций и ввести для них счетчик (см. рис. 20). в 2. О решении алгебраических уравнений 1. Действительные корни. Рассмотренные выше методы решения нелинейных уравнений пригодны как для трансцендентных, так и для алгебраических уравнений. Вместе с тем при нахождении корней многочлепов приходится сталкиваться с некоторыми особенностями. , В частности, при рассмотрении точности вычислительного процесса (см, гл. 1, з 31 отмечалась чувствительность н 11 л, и, турчак ГЛ.
5. НЕЛИНЕИНЫЕ УРАВНЕНИЯ Ы2 погрешпостям значений корней многочлена. С другой стороны, по сравнению с трансцендентными функциями многочлены имеют то препмугцество, что заранее известно число их корней. Напомним известные пз курса алгебры некоторыв свойства алгебраических уравнений с действительнымп коэффициентами вида (5.5) а„х" + а„,х" ' +... + а.,х+ а, = О. Г (х„) х+,—— х и- и и) Г(х) = а„+ а,х+...+ а.х"', Е'(х) = а, + 2а,х+...+ па„,х" '. Для вычисления значений многочленов Г (х) и Г (х) в точке х = х„может быть использована схема Горпера (см. гл.
2, ~ 2, п, 3). Естественно, при исиользоваппи метода Ньютона должны Выполняться условия сходимостп (сгк ~ 1, и. 4). При пх соблюдении в результате ропшина получается 1. Уравнение степени п имеет всего и корней, среди которых могут быть как действительные, так и комплексные. 2. Комплексныо корни ооразуют комплексно-сопряженные пары, т. е. каждому корню х = с+ Ы соответствует корень х = с — И.
3, Число положительных действительных корней меньше или равно числу перемен знаков в последовательности коэффициентов а„а„..., а„. Заменяя х на — х в уравнении (5.5), таким же спосооом можно оценить число отрицательных корней. Одним из способов решения уравнения (5.5) является метод понижения порядка. Он состоит в том, что после нахо;кдения какого-либо корня х = с данное уравнение можно разделить на х — с, понизив его порядок до и — 1. Правда, при таком способе нужно помнить о точности, поскольку да;ке небольшая погрешность в значении первого корня может привести к накапливанию погрешности В дальнешиих вычислениях. Рассмотрим применение метода Ньютона к решению уравнения (5.5).
Б соответствии с формулой (5.3) итерационный процесс для нахождения корня нелинейного уравнения (5.5) имеет вид я ". О РешГ1пп1 ллгег1РАи~1еских уРлвпе11ий 163 значение того корпя, которь1й находится волизи заданного начального приближения .т,. Заметим, что для уменьшения погрешностей лучше сначала находить меньшие по модулю корни многочлена и сразу удалять их из уравнения, приводя его к меныпей степени.
11оэтому, если отсутствует информация о величинах корней, в качестве начальных приолпженпй принимают числа О, =Е1 и т, д. 2. Комплексные корни. При использовании ЭВМ, как правило, имеется возможность раоотать с комплексныхп1 числами; поэтому изложенные методы могут быть использованы и для нахождения комплексных корней многочленов.
Если в качестве начального прполижения х„ взять комплексное число, то последующие приолп;кения и окончательное зна шние корня могут оказаться комплексными. Комплексные корпи попарно сопряженные, и прп их исключении порядок уравнения уменьшается на два, поскольку оно делится сразу на квадратный трехчлен, т. е. Г(х) = (х'+ рх+ д) (Ьпхп '-+... + Ь,)+ Ь,х+ Ь„. (5.6) Линейный остаток Ь,х+ Ь, равен пулю, если р, д выразнгь с помощью найденных корней, т. е.
р= — 2с, у=с'+У, т=с~М. Представление (5.6) может быть также использовано для нахождения р, д, а значит, и для определеппя корней. Зта процедура ле;кпт в основе метода Лина. Суть этого метода состоит в следующем. Предположим, что коэффицпен1ы Ьо Ь, равны нулю. Тогда, сравнивая коэффициенты гри одинаковых степенях х многочлена Г(т) в выражениях (5,5) и (5.6), можно получить (для упрощения вв1кладок Ъ„= а„= 1) Ь вЂ” ~=0 -~ — р, Ьп — 2 пп — 2 РЬп — $ д1 (5.7) Ь2 а2 РЬЗ ЧЬ4 р =(а, — дЬ,)Я„д = а,!Ь,. Задаем начальные приближения для р, д, которые используются для вычисления коэффициентов Ь„о Ь„2..., ..., Ь.
Затем из двух последних уравнений системы (5.7) уточняем значения р, д. Итерацпонньш процесс вычисления этих величин продолжается до тех пор, пока их из- 119 Ы4 ГЛ, 5. НЕЛПНЕЙНЫЕ УРАВНЕНИЯ меыеыпя в двух последующих итерациях не станут малыми. Таким образом, в методе Лина проводится решение двух линейных уравнений относительно Л и О по метеду итераций Гаусса — Зейделя. Широко распространен также другой метод, основанный на выделении квадратичного множителя х'+ рх+ д,— иетод Бзрстоу.
Он использует метод Ньютона для решения системы двух уравнен й, который будет рассмотрен ниже. 5 3. Системы уравнений $. Вводные замечания. В гл. 4 рассматривались системы линейных уравнений. Многие практические задачи сводятся к решению системы нелинейных уравнений. Пусть для вычисления неизвестных х„т„..., т„требуется решить систему и нелинейных уравнений Г,(т„,г„..., х„)=0, Г~(т„х2, ..., х.) =О, (5.8) Е' и (Хо Т21 ° ° 1 ~и) = О.
х„..., х.), х2р ° ° ° > тп) 1 х, =1,(х„ х, = ~,,(х„ ° ° ° ° а (5.9) В отличие от систем линейных уравпени11 не существует прямых методов решения нелинейных систем общего вида. Лишь в отдельных случаях систему (5.8) можно решить непосредственно. Например, для случая двух уравнений иногда удается выразить одно неизвестное через другое и таким ооразом свести задачу к решению одного нелинейного уравнения относительно одного непзвестного. Для решения систем нелинейных уравнений обычно используются итерационные методы.
Ния'е будут рассмотрены два из нпх — метод простой итерации и метод Ньютона. 2. Метод простой итерации, Систему уравнений (5.8) представим в виде $ 3. спствъ1ы угхвнвнпп Алгоритм решения этой системы методом простой итерации папомипает метод 1''аусса — Зейделя, используемый для решения систем линейных уравнений (см. гл. 4, $3), Пусть в результате предыдущей итерации получены значения неизвестных х, = а„х, = а„..., х — а . Тогда выражения для неизвестных на следующей итерации имеют впд т, =/,(а„а,, а„), х~ = ~л(х, а, ..., а.), Ф ° ° ° а ° ° ° в ° х; =/(х„..., х; „а;, ..., а-„), В Ю 1 ° ° ° ° ° х„= ~„(х„..., х„„а„). Итерационный процесс продолжается до тех пор, пока изменения всех неизвестных в двух последовательных итерациях пе станут малышшш, т. е. абсолютные величины их разностей пе станут меньшими заданного малого числа.
Прп использовании метода простой итерации успех во многом определяется удачным выоором начальных прпблпжешш неизвестных: опп должны быть достаточно близкими к истинному решошпо. В противном случае итерационный процесс может пе сойтись. 3. Метод Ньютона. Этот метод обладает гораздо более быстрой сходимостью, чем метод простой итерации.
В случае одного уравнения,Г(х)=0 алгоритм метода Ньютона был легко получен путем записи уравнения касательной к кривой у.= Г(х). В основе метода Ньютона для системы уравнений лежит пспользованпе разложения функций Г~(х„х„..., х„) в ряд Тейлора, причем члены, содеря'ащпе вторые (и более высоких порядков) производные, отбрасываются, Пусть приближенные значения неизвестных системы (5.8) (например, получеппые па предыдущей итерации) равны соответственно а„а„..., а„. Задача состоит в нахождении приращений (поправок) к этим значениям Лх„Лх2, ..., Лх„, благодаря которым решение системы (5,3) запишется в виде х, = а, + Лхо х, = а~+ Лх2,..., х„= а„+ Лх„. (5ЛО) Проведем разложение левых частей уравйений ' (5.8)' с учетом (5,10) в ряд Тейлора, ограничиваясь лишь ГЛ.
5, ПГЛПНГППЫГ ГРАВПГППЯ лпнейнымп чт1епамп отпос1пельно приращений: дГ, дГ Е, (х,, ...х„) ~ Г, (а„...,, а ) + — 'Лх, + ... + — 'Лх„,. "1 б7„ дГ, Р2(х„...,: и):. Гг,а,...., а„) + —.Л., + ... + — Л. „, '"1 и дГ„ дри 1 Поскольку в соответствии с (5.8)' левые частп этпх выражеппп должны обращаться в нуль, то прправняем нули и правые части. Получпм следующую спстему лп- нейньтх алгебраических уравпеппй относптельпо прпра- щенпй: дГ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
