Xreferat.com » Рефераты по математике » Итерационные методы решения систем нелинейных уравнений

Итерационные методы решения систем нелинейных уравнений

height="33" />

Следовательно,

Таким образом, имеет место неравенство

 (3.3)

По предположению индукции . Поскольку в силу условия 4)

, то

Это значит, что для , и шаг индукции реализован. Превое утверждение теоремы доказано.

Продолжим доказательство. Положим перепишем оценку (3.3) после умножения на в виде . Покажем, что

 (3.4)

Будем рассуждать по индукции. При  неравенство (3.4.) очевидно. Допустим, что оно справедливо для некоторого . Тогда

Переход  завершен, т.е. неравенство (3.4) справедливо для всех . Перепишем его в исходных обозначениях

Получили утверждение 3). При этом

, т.е. .

Это значит, что имеет место сходимость:  

Замечание 1. Неравенство (3.3) при условии  означает, что последовательность  сходится к решению  с квадратичной скоростью.

Замечание 2. Поскольку , то из утверждения 3) следует оценка погрешности метода Ньютона

Теорема. Если fi(x) непрерывны, вместе с первыми производными в выпуклой области G, содержащей решение системы $X^{ast}$и при $x= X^{ast}$матрица Fx не вырождена, то существует такая окрестность  что при любом метод Ньютона сходится к $x^{ast}$.$Box$

$x^0in R$

Доказательство. Рассмотрим

begin{eqnarray*}f_i(z)-f_i(y)&=&int^1_0frac{d}{dt}f_i(y_1+t(z_1-y_1),quady... ...um^n_{j=1}frac{partial}{partial x_j}f_i(y+t(z-y))(z_j-y_j)dt.end{eqnarray*}

Введем и матрицу  и матрицу. Очевидно, что F(x,x)= F(x), то есть имеем

$F_{ij}(y,z)=int^1_0frac{partial}{partial x_j}f_i(y+t(z-y))dt$,$F(y,z)={F_{ij}}$
 


 (12)


Есть тождества

begin{eqnarray*}f(X^{ast})&=&0,enskip X^{ast}=varphi(X^{ast})equiv X^{... ...st})f(X^{ast})\ x^{k+1}&=&varphi(x^k)=x^k-F^{-1}_x(x^k)f(x^k),end{eqnarray*}

Тогда.

begin{displaymath}x^{k+1}-X^{ast}=big[E-F^{-1}_x(x^k)F(X^{ast},x^k)big](x^k-X^{ast}).end{displaymath}

Вблизи окрестности $X^{ast}$для любого найдется такое x0, что если,. то

Тогда  

begin{eqnarray*}Vert x^k-X^{ast}Vert& leq &K^kVert x^0-X^{ast}Vert\ li... ...}Vert x^k-X^{ast}Vert&=&0,quad lim_{ktoinfty}x^k=X^{ast}.end{eqnarray*}

На начальное приближение x0 наложено труднопроверяемое условие.

${Vert x-x^0Vertleqrho}$Теорема Канторовича. Если функции fi(x) непрерывны вместе со своими 1 -ми и 2 -ми производными в некоторой выпуклой области G, содержащей точку x0 вместе с ее окрестностью и выполнены следующие условия:

в точке x0 существует матрица F-1 такая

begin{displaymath}Vert F^{-1}_x(x^0)Vert _{infty}leq M_0end{displaymath}

 

то последовательность xk+1=xk-f-1x(xk)F(xk) сходится к $X^{ast}$.$X^{ast}$является единственным решением системы f(x)=0 в области и имеет место оценка

begin{displaymath}Vert X^{ast}-x^kVert _1leq(frac{1}{2})^{k-1}h^{2^k}_0r_0.end{displaymath}$Box$

Докажем 3 неравенства

а) $Vert f(x+Delta x)-f(x)Vert _{infty}leq F_x(xi)VertVertDelta xVert$

б)$Vert F_x(x+Delta x)-F_x(x)Vertleq nNVertDelta xVert$

в) $Vert f(x+Delta x)-f(x)-F_x(x)Delta xVertleqfrac{1}{2}nNVertDelta xVert^2_{infty}$

begin{eqnarray*}Vert f(x+Deltax)-f(x)Vert&=&max_ivertsum^n_{j=1} frac{... ...ial x_j}vert\ &leq&VertDeltaxVertcdotVert F_x(xi)Vert.end{eqnarray*}


б)begin{eqnarray*}Vert F_x(x+Deltax)-F_x(x)Vert&=&max_isum^n_{j=1}vertsum... ...partial x_qpartial x_k}vertleq nNVertDeltaxVert _{infty}.end{eqnarray*}

begin{eqnarray*}Vert f(x+Delta x)-f(x)-F_x(x)Delta xVert&=&max_ivert f_i... ...al x_k}vert\ &leq&frac{n}{2}cdotVertDelta xVert^2cdot N.end{eqnarray*}

в)

begin{displaymath}Vert x^1-x^0Vert=Vert F^{-1}_x(x^0)f(x^0)VertleqVert F^{-1}_xVertVert f(x^0)VertleqM_0delta=r_0<frac{rho}{2}.end{displaymath} 

begin{eqnarray*}Vert E-F^{-1}_x(x^0)F_x(x^1)Vert&=&Vert F^{-1}_x(x^0)(F_x(x... ...0Vert\ &leq&nr_0M_0N\ &=& frac{h_0}{2}\ &leq&frac{1}{2},end{eqnarray*} 

т.е. матрица F-1x(x0)Fx(x1) невырождена, и


begin{displaymath}Vertbig[F^{-1}_x(x^0)F_x(x^1)big]^{-1}Vertleqfrac{1}{1-h_0/2}leq 2.end{displaymath}

begin{displaymath}Vert EVert-Vert AVertleqVert E-AVert,quad1-alphal... ...rt A^{-1}Vertleqfrac{1}{Vert AVert}leqfrac{1}{1-alpha}end{displaymath}

begin{displaymath}F^{-1}_x(x^1)=big[F^{-1}_x(x^0)F_x(x^1)big]^{-1}F^{-1}_x(x^0)end{displaymath} и

begin{displaymath}Vert F^{-1}_x(x^1)Vertleq 2cdot M_0.end{displaymath}

Fx(x0)(x1-x0)+f(x0)=0

begin{displaymath}Vert f(x^1)VertleqVert f(x^1)f(x^0)-F_x(x_0)(x^1-x^0)Vertleqfrac{1}{2}nNcdot r^2_0end{displaymath}

begin{displaymath}Vert F^{-1}(x^1)f(x^1)Vertleqfrac{1}{2} nNcdotr^2_0cdot 2M_0=(M_0nr_0N)r_0=frac{h_0r_0}{2}leqfrac{r_0}{2}.end{displaymath}

Покажем, что при всех k имеют место неравенства:

 (А)

begin{displaymath}Vert F^{-1}_x(x^k)Vertleq 2M_0;quad Vert f(x^k)Vertleqfrac{nNr^2_0}{2^{2k-1}}h^{2^k-2}_0leqfrac{nNr^2_0}{2^{2k-1}}.end{displaymath}

begin{displaymath}Vert F^{-1}_x(x^k)f(x^k)Vertleqfrac{r_0}{2^k} mbox{, при }k=1mbox{ ужепоказали.}end{displaymath}

Пусть имеет место m=k-1

begin{eqnarray*}Vert x^{m+1}-x^mVert&=&Vert F^{-1}_x(x^m)f(x^m)Vertleqfr... ...1}}+ldots+frac{r_0}{2}+r_0<2r_0leqrho_0; x^{m+1}in R_0(x_0)end{eqnarray*}

Повторим неравенства

begin{eqnarray*}Vert E-F^{-1}_x(x^m)F_x(x^{m+1})Vert&leq& 2^mM_0nNfrac{r_0... ...{2^m-2}_0=frac{h^{2^m-1}_0r_0}{2^{m+1}}leqfrac{r_0}{2^{m+1}}.end{eqnarray*}

Неравенство (А) показывает, что в круге R последовательность xk является фундаментальной, т.е. имеется предел.

Оценим сходимость

begin{eqnarray*}Vert x^{k+p}-x^kVert&leq&Vert x^{k+p}-x^{k+p-1}Vert+ldot... ...ldots+frac{1}{2^{p-1}}big]leqfrac{r_0}{2^{k-1}}h^{2^k-1}_0,end{eqnarray*}т.е.,

устремляя правая часть не меняется,, т.е. при очень хорошая сходимость.

2.3.1 Модификации метода ньютона

1. Вычисления в методе Ньютона гораздо сложнее, чем при простых итерациях, т.к. на каждой итерации требуется находить матрицу производных и решать систему линейных уравнений. Поэтому рекомендуется такой приём: матрица Якоби вычисляется только на начальном приближении. Однако сходимость при этом видоизменении становится линейной, причём обычно не с малой константой, ибо матрица производных на начальной итерации может заметно отличаться от окончательной. Поэтому скорость сходимости заметно уменьшается и требуемое сисло итераций возрастает.

2. В ещё одной модификации итерационную формулу метода Ньютона вводится параметр  следующим образом

На каждой итерации  находится так, чтобы уменьшить невязку уравнения (3.1), т.е. выполнить неравенство

 (3.5)

Проведём обоснование такой процедуры в евклидовой норме.

Ведём в рассмотрение функцию-невязку для уравнения (3.1)

Найдём градиент , используя представление

С этой целью выделим главный член приращения

Следовательно, по определению

Обозначим  и найдём производную функции  в точке по направлению :

если .

Таким образом, – есть направление спуска для функции в точке  для малых . Это значит, что выбор шага  согласно условию (3.5) возможен.

2.3.2 Квазиньютоновкие методы

Одним из недостатков метода Ньютона является необходимость вычислять матрицу Якоби и решать систему линейных алгебраических уравнений. Это требует значительных расходов машинных действий, объём которых резко возрастает с увеличением размерности системы. Поэтому были разработаны модификации метода Ньютона, в которых на протяжении итерационного процесса вместо построения самой матрицы Якоби или её обратной строится их аппроксимация. Это позволяет существенно сократить количество арифметических действий на итерации. Такие методы решения систем нелинейных уравнений получили название квазиньютоновских. Большинство известных квазиньютоновских методов сходится локально с надлинейной скоростью сходимости при тех самых предположениях о свойствах функции , которые были сделаны при использовании метода Ньютона, который имеет квадратичную скорость сходимости. Квазиньютоновские методы можно разделить на два тесно связанных между собой класса методов в зависимости от того, что аппроксимируется - матрица Якоби или ей обратные.

Рассмотрим первый из классов, где матрица Вк с размерами п х п аппроксимирует матрицу . Перед началом итераций задают начальную точку а матрицу Во обычно получают, или допуская, что она является единичной, или аппроксимируя  конечно-разностными формулами. Потом для k = 0, 1.... вычисляют

 

Где  — n- мерный вектор, который является параметром рассматриваемого класса методовв. Если  взять таким, что равняется ,то будем иметь первый метод Бройдена. Выбор  соответствует методу Пирсона, а  — симметрическому методу первого ранга.

Во втором из рассматриваемых здесь классов квазиньютоновских методов матрица с размерами п х п аппроксимирует матрицу . Перед началом итерации задают начальную точку х{0) и матрицу , которая обычно или равна единичной, или является обратной к конечно-разностной аппроксимации . Потом вычисляют

где — n-мерный вектор, который является параметром рассматриваемого класса методов. Конкретный вид вектора  отвечает соответствующему методу: например, — второму методу Бройдена,  — методу Мак-Кормика.

Заметим, что если задать  то можно вести перерасчет не Вк, а матриц  по формуле

 (3.30)

эквивалентной (3.27). Это требует порядка 0(п2) арифметических действий вместо 0(п3), необходимых для решения системы линейных уравнений .

Как видно из (3.30), между формулами (3.27) и (3.29) имеет место определенная связь. Так.если , то  при . Таким образом, один и тот же метод может реализоваться двумя разными формулами (3.27) и (3.29), которые эквивалентные теоретически, но их численная реализация может отличаться по эффективности.

Рассмотрим, например, первый метод Бройдена. Его можно реализовать по формуле (3.27) так, что это потребует в общем 0(n3) арифметических действий. Это оказывается возможным, если подать матрицу Вк в виде произведения , где — ортогональная, а — верхняя треугольная матрица. Действительно, в этом случае решение системы нуждается в только 0(n3) арифметических действий. Имея, на представление матрицы Вк+1, которая удовлетворяет (3.27) в виде , необходимо 0(п2) арифметических действий. Важное преимущество формулы (3.27) перед (3.39) заключается в том, что в (3.27) нет необходимости умножения матрицы на вектор, поскольку

Существуют квазиньютоновские методы, которые учитывают симметричность матрицы Якоби и вырабатывают последовательность симметричных матриц Вк, (или). Эти методы также можно разделить на два класса. В первом из них матрица Вк аппроксимирует F(х). В отличие от описанного выше класса, который задается формулами (3.26) и (3.27), здесь нужна симметричность матрицы Во, и вместо (3.27) используется формула

где значение параметра отвечает симметричному варианту Пауелла методу Бройдена, а — методу Давидона - Флечера - Пауелла.

Во втором из рассматриваемых классов квазиньютоновских методов матрица Нк аппроксимирует матрицу . Здесь матрица Но должна быть симметричной, а вместо (3.29) используется формула

Где соответствует методу Бройдена-Флечера-Голвдфарба-Шенно, что является одним из наилучших (с вычислительной точки зрения), который учитывает симметричность матрицы Якоби.

Описанные выше квазиньютоновские методы сходятся лишь при достаточно хорошом начальном приближении х(0). Для расширения области их сходимости можно использовать прием, который имеет название одномерного поиска.

Пусть имеем квазиньютоновское направление (или ). Используем длину шага = 1 и проверим неравенство

 (3.34)

где - евклидовая норма. Если оно выполняется, то заканчиваем одномерный поиск и считаем

 (3.35)

т.е. уменьшаем длину шага (устанавливая, например, ), пока не выполнится (3.34). На этом заканчиваем одномерный поиск и переходим к формуле (3.35).

Как видим, одномерный поиск (в случае успеха) обеспечивает монотонное уменьшение нормы отклонения  с ростом к. Если квазиньютоновское направление  сильно отличается от ньютоновского, то одномерный поиск может оказаться неудачным, и тогда необходимо возобновить матрицу Вк, (или)., приравняв ее, например, конечно-разносной аппроксимации матрицы Якоби (или ). Критерием окончания итераций для квазиньютоновских методов есть неровность


3. Другие итерационные методы решения систем нелинейных уравнений

3.1 Метод Пикара

Существуют также итерационные методы решения систем нелинейных уравнений, которые учитывают вид конкретной системы.

Так, если в уравнениях системы можно выделить линейную l(X) и нелинейную g(X)части функций fi(X) = li(X) + gi(x), то удобней применить к ней метод Пикара.

В таком случае систему уравнений можно записать в виде

 

li(X) = - gi(X), i=1,2,3...n;

или в векторной форме A X= - G(X);

где A- матрица коэффициентов

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Страницы: 1 2 3

Похожие рефераты:

  • Исследование метода простой итерации и метода Ньютона для решения систем двух нелинейных алгебраических уравнений

    Сравнение методов простой итерации и Ньютона для решения систем нелинейных уравнений по числу итераций, времени сходимости в зависимости от выбора начального приближения к решению и допустимой ошибки. Описание программного обеспечения и тестовых задач.

  • Существование решения дифференциального уравнения и последовательные приближения

    Теорема существования и единственности решения уравнения.

  • Нахождение корня нелинейного уравнения. Методы решения системы нелинейных уравнений

    Приближенные значения корней. Метод дихотомии (или деление отрезка пополам), простой итерации и Ньютона. Метод деления отрезка пополам для решения уравнения. Исследование сходимости метода Ньютона. Построение нескольких последовательных приближений.

  • Поиск нулей функции. Итерационные методы

    Поиск нулей функции - исследование и построение различных функций зависимостей. Исследование непрерывных процессов. Метод простой итерации. Итерационный процесс Ньютона, аналитическое задание системы уравнений и локализация области нахождения корня.

  • Численные методы

    Интерполяционная схема Эйткина. Связь конечных разностей и производных. Распространение ошибки исходных данных при вычислении конечные разности. Свойства разделенной разности. Интерполяционная формула Ньютона для не равноотстоящих узлов. Полином Лагранжа.

  • Итерационные методы решения системы линейных алгебраических уравнений

    Решение системы линейных алгебраических уравнений большой размерности с разреженными матрицами методом простого итерационного процесса. Понятие нормы матрицы и вектора. Критерии прекращения итерационного процесса. Выбор эффективного итерационного метода.

  • Методы решения алгебраических уравнений

    Итерационные методы (методы последовательных приближений) для решения уравнений. Одношаговые итерационные формулы. Метод последовательных приближений Пикара. Возникновение хаоса в детерминированных системах. Методы решения систем алгебраических уравнений.

  • Метод простых итераций с попеременно чередующимся шагом

    Особенности ариорного выбора числа итераций в методе простых итераций с попеременно чередующимся шагом для уравнений I рода. Анализ и постановка задачи. Сходимость при точной правой части. Сходимость при приближенной правой части. Оценка погрешности.

  • Методы спуска

    Решение задач безусловной минимизации методами спуска: метод градиентного и покоординатного спуска.

  • Методы решения систем линейных уравнений

    Метод последовательного исключения неизвестных (метод Гаусса) при решении задач аппроксимации функции в прикладной математике. Метод Гаусса с выбором главного элемента и оценка погрешности при решении системы линейных уравнений, итерационные методы.

  • Исследование метода дифференцирования по параметру для решения нелинейных САУ

    Разработка программного обеспечения для решения нелинейных систем алгебраических уравнений методом дифференцирования по параметру и исследование влияние метода интегрирования на точность получаемого решения. Построение графиков переходных процессов.

  • Приближённые методы решения алгебраического уравнения

    Численное решение уравнения, условия, наложенные на функцию, графический метод определения корней. Метод дихотомии. Метод итераций. Быстрота сходимости процесса итераций. Метод касательных. Первые приближения для метода касательных.

  • Численные методы для решения нелинейных уравнений

    Изучение численных методов приближенного решения нелинейных систем уравнений. Составление на базе вычислительных схем алгоритмов; программ на алгоритмическом языке Фортран - IV. Приобретение практических навыков отладки и решения задач с помощью ЭВМ.

  • Итерационные методы решения систем линейных алгебраических уравнений

    Сущность итерационного метода решения задачи, оценка его главных преимуществ и недостатков. Разновидности итерационных методов решения систем линейных алгебраических уравнений: Якоби, Хорецкого и верхней релаксации, их отличия и возможности применения.

  • Приближённое решение алгебраических и трансцендентных уравнений

    Общая постановка задачи. Отделение корня. Уточнение корня. Метод половинного деления (бисекции). Метод хорд (секущих). Метод касательных (Ньютона). Комбинированный метод хорд и касательных. Задания для расчётных работ.

  • Метод релаксации переменных решения СЛАУ

    Методы решения систем линейных уравнений. Метод Якоби в матричной записи. Достоинство итерационного метода верхних релаксаций, вычислительные погрешности. Метод блочной релаксации. Разбор метода релаксаций в системах линейных уравнений на примере.

  • Прямые методы решения систем линейных алгебраических уравнений

    Характеристика и использование итерационных методов для решения систем алгебраических уравнений, способы формирования уравнений. Методы последовательных приближений, Гаусса-Зейделя, обращения и триангуляции матрицы, Халецкого, квадратного корня.

  • Исследование метода продолжения решения по параметру для нелинейных САУ

    Поиск корней нелинейных САУ с помощью метода продолжения решения по параметру. Математическое описание метода. Программное обеспечение для построения графиков сходимости метода. Требования к программному обеспечению и описание логической структуры.

  • Математический анализ

    Исследование заданной функции и построение ее графика. Расчет объема тела, полученного вращением вокруг оси абсцисс фигуры, ограниченной линиями и осями координат. Вычисление интеграла при заданной силе. Работа, которую нужно совершить для сжатия пружины.

  • Решение одного нелинейного уравнения

    Методы решения одного нелинейного уравнения: половинного деления, простой итерации, Ньютона, секущих. Код программы решения перечисленных методов на языке программирования Microsoft Visual C++ 6.0. Применение методов к конкретной задаче и анализ решений.