Министерствообщего и профессионального образования Российской Федерации
Саратовскийгосударственный технический университетЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
Методическиеуказания
ксамостоятельной работе по курсу «Высшая математика»
для студентоввсех специальностей
под контролемпреподавателя
Одобрено
редакционно-издательскимсоветом
Саратовскогогосударственного
техническогоуниверситета
Саратов 2008
Введение
Данная работаориентирована на изучение некоторых численных методов приближенного решениясистем нелинейных уравнений с любым числом уравнений, составление на базе этихметодов вычислительных схем алгоритмов и программ на алгоритмическом языкеФОРТРАН – IV.
Методические указаниямогут быть использованы как в процессе выполнения курсовой работы, так и длярешения практических задач.
Задача настоящих указанийсостоит в том, чтобы научить студентов решать системы нелинейных уравнений спомощью ЭВМ и затем полученные навыки использовать в курсовом и дипломномпроектировании.
Предполагается, чтостуденты прослушали лекционный курс по основам алгоритмического языка ФОРТРАН –IV.
В качестве справочногопособия по языкам программирования может быть использована литература. [5]
Численныеметоды для решения нелинейных уравнений
Цель работы: изучение численных методовприближенного решения нелинейных систем уравнений, составление на базе вычислительныхсхем алгоритмов; программ на алгоритмическом языке ФОРТРАН – IV, приобретение практических навыковотладки и решения задач с помощью ЭВМ.
1.Определения и условные обозначения
/> – конечномерноелинейное пространство, элементами (точками, векторами) являются группы из /> упорядоченных действительных чисел,например:
/>
где /> – действительные числа, />.
В /> введена операциясложения элементов, т. е. /> определеноотображение />,
где />
Оно обладает следующимисвойствами:
1. />,
2. />,
3. /> , что /> (элемент/> называется нулевым),
4. />, что /> (элемент/> называется противоположнымэлементу />).
В /> введена операцияумножения элементов на действительные числа, т.е. /> определеноотображение />,
где />
Оно обладает следующимисвойствами:
1. />,
2. />
Операции сложения элементов иумножения их на числа удовлетворяют законам дистрибутивности:
1. />,
2. />.
Каждой паре элементов /> поставлено в соответствиедействительное число, обозначаемое символом /> иназываемое скалярным произведением, где
/>
и выполнены следующие условия:
1. />,
2. />,
3. />,
4. />, причем /> –нулевой элемент.
Матрица /> вида
/>/> , (1)
где />– действительные числа (/>,/>) определяет линейныйоператор, отображающий линейное пространство /> в себя, а именно, для />
/>,
где />.
Над линейнымиоператорами, действующими в линейном пространстве />,вводятся следующие операции:
1. сложениеоператоров />, при этом, если />, то />,
2. умножениеоператоров на числа: /> при этом, если />, то />,
3. умножениеоператоров: />, при этом, если />, то />.
Обратным к оператору /> называется оператор /> такой, что />, где /> – единичный оператор,реализующий тождественное отображение, а именно,
/>.
Пусть число /> и элемент />, таковы, что />.
Тогда число /> называется собственнымчислом линейного оператора />, аэлемент /> – собственным векторомэтого оператора, соответствующим собственному числу />.
Линейный оператор /> называется сопряженным коператору />, если для любых элементов /> выполняется равенство />.
Для всякого оператора /> сопряженный оператор /> существует, единствен;если />, то />.
Справедливы равенства:
1. />,
2. />,
3. />,
4. />, если /> существует.
Каждому элементу /> ставится в соответствиедействительное положительное число, обозначаемое символом /> и называемое нормойэлемента />.
Введем в рассмотрение тринормы для />:
/>,
/>,
/>.
При этом выполняются следующиенеравенства:
/>.
Норма элемента удовлетворяетследующим условиям (аксиомам нормы):
1. />, причем />,лишь если />,
2. />,
3. />.
Говорят, что последовательностьэлементов /> сходится к элементу />,
а именно, />,
или />,
если />.
Определенная такимобразом сходимость в конечномерном линейном пространстве /> называется сходимостью понорме.
Множество элементов />, удовлетворяющихнеравенству /> называется замкнутым(открытым) шаром в пространстве />сцентром в точке /> и обозначается />.
Каждому линейномуоператору, определяемому квадратной матрицей (1), ставится всоответствие действительное неотрицательное число, обозначаемое символом /> и называемое нормойлинейного оператора />.
Норма линейного оператораудовлетворяет следующим условиям аксиомам норм:
4.4 />, причем />,лишь если /> – нулевая матрица,
4.4 />,
4.4 />.
Введем в рассмотрение тринормы для А отображающего /> в />:
/>,
/>,
/>,
где /> i-ое собственное значение матрицы />.
Эти нормы линейногооператора А согласованы с соответствующими нормами элемента (вектора) /> в смысле условия />.
2.Основные сведения о системах нелинейных уравнений в />
Общая форма системнелинейных уравнений в /> имеет вид:
/> (2)
или F(x) = 0,
где /> – заданные функции n переменных,/> – неизвестные.
Функция /> при действительных значенияхаргументов принимают действительные значения, т.е. являютсядействительнозначными. Вычислять будем только действительные решения.
Решением системынелинейных уравнений (2) называется совокупность (группа) чисел />, которые, будучиподставлены на место неизвестных />,обращают каждое уравнение системы в тождество.
Частным случаем системы (2)является система линейных уравнений:
/>
или />,
где А – матрицавида (1), порождающая линейный оператор, отображающий /> в />
/>
Система линейныхуравнений (2) поставим в соответствие линеаризованное уравнение (первыедва члена из разложения в ряд Тейлора (2)) в точке /> вида
/> (2/>)
или />,
где /> – квадратная матрицаЯкоби, составленная из частных производных первого порядка функций, а именно />, вычисленных точке />.
Длядальнейшего нам потребуется еще одна форма записи системы нелинейных уравненийв />, а именно:
/> (3)
или />,
где />.
Операции, с помощьюкоторых осуществляется преобразование системы (2) к системе (3),могут быть любыми, необходимо только, чтобы искомое решение системы (3) удовлетворялосистеме (2).
Функции /> удовлетворяют тем жеусловиям, что и функции />.
3. Отделениерешений
Задача отделения решений системнелинейных уравнений состоит в определении достаточно малой окрестности (шарамалого радиуса, центром которого является решение) около какого-нибудь одногорешения и в выборе в этой окрестности начального приближения к решению.Начальное приближение должно попасть при этом в область сходимости метода.
Задача отделения решений не имеетдостаточно эффективных методов общего характера. При решении уравненияпредполагается знание начальных приближений к изолированному решению изпостановки конкретной задачи. Если же таких данных нет, то можно дать лишьнекоторые рекомендации для конкретных видов уравнений.
Так, если дано скалярноеуравнение />, то его решение сгеометрической точки зрения можно рассматривать как абсциссы точек пересеченияграфика функции с осью абсцисс. Построив график функции y=f(x), приближенно определяем окрестности изолированных точекпересечения графика с горизонтальной осью. Сами точки пересечения берем заначальные приближения к точным решениям.
Безусловно, графические построенияимеют большие погрешности, и выбранные начальные приближения могут не попасть вобласть сходимости применяемого метода.
Тогда нужно провестипробные решения на ЭВМ выбранным методом с исследованием сходимости.
Если приближения сходятся, тоначальные приближения выбраны в области сходимости метода и можно получитьприближенное решение с заданной точностью.
Если приближениярасходятся, следует провести более точные графические построения и выбратьначальное приближение в области сходимости.
Аналогично отделяютсярешения для системы двух нелинейных уравнений
/> , />.
В этом случае наплоскости x,y строятся линии уровня функции двух переменных /> и />. Координаты точекпересечения графиков этих функций дают начальные приближения изолированныхрешений.
4. Методырешения нелинейных уравнений
4.1 Методпростой итерации
Метод простой итерации(см. [1]) применяется для решения систем нелинейных уравнений с любым числомуравнений. Его можно применять как для уточнения найденного решения, так и дляпервоначального нахождения решения. В последнем случае, однако, метод может недать результата.
Для применения методапростой итерации система уравнений (2) приводится к виду (3).
Затем, взяв начальноеприближение />, которое предполагаетсялибо известным, либо произвольным, строим последовательность
/> (4)
по следующим формулам
/> (5)
Замечание. Для приведениясистемы уравнений (2) к виду (3) можно использовать прием:
/>
где /> – релаксационный параметр,определяется методом Зейделя.
4.2 МетодЗейделя
Метод Зейделя отличается от методапростой итерации тем, что вычисления ведутся по формулам:
/> (6)
Иными словами, привычислении /> используются не />, как в методе простойитерации, а />.
4.3 МетодНьютона
Этот метод (см.[1], [4]) предложенИ.Ньютоном в 1669 году, однако наиболее полное обоснование было сделаносоветским математиком Л.В.Канторовичем в 1949 году (см.[4]), поэтому в литературеэтот метод часто называют методом Ньютона-Канторовича.
Метод Ньютона являетсяодним из итерационных методов, получаемых линеаризацией линейного оператора
/>,
где /> из уравнения (2).
Так, для к-го приближения /> к точному решению /> уравнения (2)ставится в соответствие линеаризованное уравнение вида (2/>), а именно:
/>
или />,
где /> –квадратная матрица Якоби, составленная из частных производных первого порядкафункций, /> т.е. />, вычисленных в точке />.
Таким образом, последовательность (4)строится по следующим правилам:
/> (),
где /> –обратный оператор к линейному оператору />,определяемому квадратной матрицей
/>
Трудности построения алгоритма методаНьютона, связанные с обращением производной /> (построение/>), обычно преодолеваютсятем, что вместо методов обращения матрицы />решаюталгебраическую систему уравнений (7) относительно неизвестных />. Алгоритмы решения системылинейных алгебраических уравнений хорошо отработаны, для них имеютсястандартные программы для ЭВМ и, кроме того, в результате решения системыодновременно с обращением матрицы получается умножение обратной матрицы навектор />.
Итерационная формула метода Ньютонапри таком подходе будет иметь вид:
/> (7)
/> . (8)
4.4 Модифицированный метод Ньютона
Эта разновидность метода Ньютонастроится путем определения производной только в одной точке приближенногорешения, т. е. Последовательные приближения (4) строятся по формулам:
/>, (9)
где /> –начальное приближение к точному решению />.
4.5Метод Зейделя на основе линеаризованного уравнения
Итерационная формула для построенияприближенного решения нелинейного уравнения (2) на основелинеаризованного уравнения (7) имеет вид:
/>
4.6 Метод наискорейшего спуска
Методы спуска (см. [2]) сводятрешение системы (2) к задаче нахождения минимума специально построенногофункционала (функционал – отображение /> вR), а именно:
/>,
где />.
Функционал в конечном пространстве Rn можно рассматривать как функциюмногих переменных />.
Для нахождения точки />, в которой функционал fпринимает минимальное нулевое значение, выбирают точку/>, находят /> и строят итерационнуюформулу: /> с начальным приближением />.
В итерационной формуле параметр hk пока не определен, выберем его такимобразом, чтобы выполнилось условие: />,начиная с x, в предположении, что f – монотонный функционал.
Для выбора hk построим функционал, зависящий отпараметра, который изменяется непрерывно: />.
При h=0 имеем, что f(0) – линия уровня функционала, проходящая через точку xk. Для нахождения следующей линииуровня, более близкой к минимуму, будем выбирать h таким образом, чтобы для данного xk
/>
Это условие минимума по h будем рассматривать как уравнениедля получения hk.
Решим его приближенно, т.к. ошибка внесколько процентов обычно не влияет на скорость сходимости. Отметим кстати,что число hkвсегдадолжно бытьположительным. Для этого разложим функцию /> вряд Тейлора по h в точке h=0 и возьмем только линейную частьэтого разложения
/>.
Подстановка линейной части в условие />, дает уравнение дляприближенного определения
/>.
Решая построенное уравнениеотносительно h, получим:
/> или />.
Таким образом, итерационная формуламетода наискорейшего спуска имеет вид:
/> или />, где производные /> вычислены в точке />.
Метод наискорейшего спуска требуетбольшего количества вычислений, чем другие методы первого порядка. Однако онобладает по сравнению с другими методами важным преимуществом, заключающемся внеизбежной сходимости процесса. При этом нужно помнить, что метод наискорейшегоспуска может привести не к решению системы уравнений (2), а к значениямаргумента, дающим относительный экстремум функции
/>, т.е. />.
5.Сходимость методов решения нелинейных уравнений
Если метод сходится, тоесть />, где
/> – точное решение
/> – k-тое приближение к точному решению, то итерационный процессследовало бы закончить по достижению заданной погрешности />, где e – заданная точность (погрешность).
Однако практически этоусловие выполнить нельзя, так как /> неизвестно,тогда для окончания итерационного процесса можно воспользоваться неравенствами />, или />, где /> и /> – заданные величины.
При таком окончанииитераций погрешность может возрасти по сравнению с /> и,поэтому, чтобы не увеличивалась, величины /> и/>соответственно уменьшаютили увеличивают число итераций.
Методы простой итерации,Зейделя, модифицированный метод Ньютона, метод наискорейшего спуска (см. [1],[2], [3], [4]) являются методами первого порядка – этозначит, что имеет место неравенство />, k=1, 2,..., где /> – константа, своя укаждого метода, зависящая от выбора начального приближения />, функции fi,i = 1, 2,..., n, и их частных производных первого и второго порядков– точнее их оценок в некоторой окрестности искомого решения, которойпринадлежит начальное приближение.
Метод Ньютона являетсяметодом второго порядка, то есть для него имеет место неравенство />, k=1, 2,..., где /> – константа, зависящая оттех же величин, что и константа />.
А теперь рассмотримдостаточные условия сходимости метода простой итерации и метода Ньютона.
Сходимость процессапростой итерации зависит от двух условий. Первое условие состоит в том, чтокакая-нибудь точка /> должна оказатьсяблизкой к исходному решению />.Степень необходимой близости зависит от функций j1, j2,..., jn. Это требование не относится ксистемам линейных уравнений, для которых сходимость процесса простой итерациизависит только от второго условия.
Второе условие связано сматрицей, составленной из частных производных первого порядка функций j1, j2,..., jn– матрицей Якоби
/> ,
вычисленных в точке />.
В случае, когдарассматривается система линейных алгебраических уравнений, матрица M состоит из постоянных чисел – коэффициентов,стоящих при неизвестных в правой части уравнения (3). В случаенелинейных уравнений элементы /> матрицыM зависят, вообще говоря, от />. Для сходимости процессапростой итерации достаточно, чтобы выполнялось неравенство: /> для /> из некоторой окрестноститочного решения />, которой должнопринадлежать начальное приближение />.
Приведем такжедостаточные условия сходимости метода Ньютона для системы уравнений вида (2)по норме />.
Предположим, что имеетсяначальное приближение />к искомому решениюсистемы (2) />, функции /> непрерывны и имеютнепрерывные частные производные до второго порядка в шаре />, тогда, если выполнены условия:
1) Матрица Якоби /> системы (2) наначальном приближении имеет обратную /> иизвестна оценка нормы обратной матрицы />,
2) Для всех точекшара /> выполнено неравенство
/> при i, j = 1, 2,..., n ,
3) Выполненонеравенство
/>,
где L – постоянная 0 £ L £ 1,
4) Числа b, N, rподчинены условию a= nbNr (2)в шаре /> имеет единственноерешение, к которому сходятся последовательные приближения (8) или (7’), (9’).
Для других методовусловия сходимости имеют сложный вид, и мы отсылаем читателя к специальнойлитературе [1], [2], [3], [4].
6.Примерный перечень возможных исследований
1) Сравнениеразличных методов на экономичность при решении конкретной задачи:
· по числу операцийна одной итерации;
· по числу итераций,необходимых для достижения заданной точности;
2) Зависимость числаитераций для достижения заданной точности:
· от выбора виданормы;
· от выборакритерия окончания итерационного процесса по /> илипо невязке /> ;
· от выбораначального приближения;
· от погрешностизадания коэффициентов в уравнении.
7.Контрольные вопросы
1) Понятие онелинейных системах уравнений в Rn.
2) Понятиеприближенного и точного решения нелинейной системы уравнений.
3) Сущностьграфического метода отделения решения для системы двух нелинейных уравнений,каковы его преимущества и недостатки?
4) Сущность методапростой итерации и метода Зейделя. Каковы условия применимости метода простойитерации?
5) Сущность методаНьютона и его модификации. Какова скорость сходимости метода Ньютона?
6) Сущность методанаискорейшего спуска. Как выбирается параметр спуска?
8. Порядоквыполнения курсовой работы
1) Получить вариантзадания, индивидуальный для каждого студента, у преподавателя, а именно:
Найти решение системынелинейных уравнений в первой координатной четверти с номером – N1 (см. варианты заданий п.10),применив для первого этапа уточнения метод с номером – N2, а для второго этапа уточнения методс номером – N3, точность вычислений на первом этапе – EPS1Î[0.1 – 0.01], на втором этапе – EPS2 Î [0.1 — 0.0001], N4 – номер нормы, I –номер параметра a, J – номер параметра b, начальное приближение выбратьпроизвольно или графически, aÎ(0,1).
2) Разработатьобязательные для выполнения задания разделы данных методических указаний.