Обсуждение:Метод Гаусса — Зейделя решения системы линейных уравнений

Материал из Википедии — свободной энциклопедии

С точки зрения русского языка слова «останов» и «остановка» являются синонимами, и первое в простой речи практически не употребляется в пользу второго, однако в прикладной математике (численные методы и методы оптимизации в частности) употребляется именно термин «останов», обозначающий завершение процедуры выполнения алгоритма. Поправте меня, если это не так.solitary dreamer 20:49, 3 февраля 2008 (UTC)

а это точно С? Там какое-то странное объявление converge, не то функция, не то еще что-то.

Си. converge — логическая функция, объявленная выше. Далее идет цикл, пока она не будет false.

217.66.145.207 06:03, 2 апреля 2009 (UTC)

Теорема о сходимости метода[править код]

Предлженное услове сходимости метода неверно! Кто-нибудь знает источник откуда взята теорема?

Заметьте, что умножение обратной матрицы от (L + D) на U (верхнетреугольную с нулевыми главными элементами) даст в первом столбце матрицы A2{\displaystyle \mathrm {A} _{2}\!} сплошные нули, и соответственно определитель = 0.

В общем случае матрица A должна быть симметрична и положительно определена; или же её главные элементы должны доминировать… Olv33 04:07, 19 ноября 2009 (UTC)

Алгоритм на языке Паскаль неверен. Пожалуйста, разберитесь с этой проблемой.

Автор сообщения: УГАТУ 193.233.144.5 03:54, 24 сентября 2010 (UTC)

нормальному человеку влом выводить каждое уравнение, поэтому он задаёт решение хитрым образом. Если присмотреться к уравнениям, то можно узреть закономерность212.3.159.168 10:59, 28 декабря 2012 (UTC)

Там где for (int j = i; j < n; j++) должно быть for (int j = i + 1; j < n; j++) у нас же c_ij = 0 при i == j. (Если что — проверяла, в приведенном варианте не работает, с поправкой работает.) 212.34.63.3 06:47, 14 мая 2014 (UTC)мимо

Здравствуйте! Похоже у вас код на с++ и на паскале соотвествует разным методам: на с — метод Зейделя, на паскале — метод итерации

Метод Гаусса — Вики

Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы^[1].

История

Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах».^[2]

Описание метода

Пусть исходная система выглядит следующим образом:

{a11x1+…+a1nxn=b1…am1x1+…+amnxn=bm{\displaystyle \left\{{\begin{array}{lcr}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_{m1}x_{1}+\ldots +a_{mn}x_{n}&=&b_{m}\\\end{array}}\right.}

Её можно записать в матричном виде:

Ax=b,{\displaystyle Ax=b,}

где

A=(a11…a1n…am1…amn),x=(x1⋮xn),b=(b1⋮bm).(1){\displaystyle A=\left({\begin{array}{ccc}a_{11}&\ldots &a_{1n}\\\ldots &&\\a_{m1}&\ldots &a_{mn}\end{array}}\right),\quad x=\left({\begin{array}{c}x_{1}\\\vdots \\x_{n}\end{array}}\right),\quad b=\left({\begin{array}{c}b_{1}\\\vdots \\b_{m}\end{array}}\right).\quad (1)}

Матрица A{\displaystyle A} называется основной матрицей системы, b{\displaystyle b} — столбцом свободных членов.

Тогда, согласно свойству элементарных преобразований над строками, основную матрицу этой системы можно привести к ступенчатому виду (эти же преобразования нужно применять к столбцу свободных членов):

{α1j1xj1+α1j2xj2+…+

Метод Гаусса (оптимизация) — Википедия

Материал из Википедии — свободной энциклопедии

Метод Гаусса^[1] — прямой метод решения задач многомерной оптимизации.

Описание

Пусть необходимо найти минимум действительнозначной функции f(x→)→minx→∈Rn{\displaystyle f({\vec {x}})\to \min _{{\vec {x}}\in \mathbb {R} ^{n}}}, а x→0{\displaystyle {\vec {x}}_{0}} — начальное приближение.

Суть метода заключается в том, чтобы на каждой итерации по очереди минимизировать функцию вдоль каждой из координат, то есть:

x→0k+1=x→k{\displaystyle {\vec {x}}_{0}^{k+1}={\vec {x}}_{k}}

{x→1k+1=x→0k+1+λ1e→1,λ1=arg⁡minλf(x→0k+1+λ1e→1)…x→nk+1=x→n−1k+1+λne→n,λn=arg⁡minλf(x→n−1k+1+λne→n){\displaystyle \left\{{\begin{array}{rl}{\vec {x}}_{1}^{k+1}={\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1},&\lambda _{1}=\arg \min _{\lambda }f({\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1})\\\ldots &\\{\vec {x}}_{n}^{k+1}={\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n},&\lambda _{n}=\arg \min _{\lambda }f({\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n})\end{array}}\right.},

где e→1,…,e→n{\displaystyle {\vec {e}}_{1},\ldots ,{\vec {e}}_{n}} — ортонормированный базис в рассматриваемом пространстве.

Таким образом метод как бы «поднимется» по координатам, используя на шагах одной итерации для вычисления следующей координаты точки приближения все предыдущие значения координат, вычисленные на той же итерации, в этом и состоит схожесть с одноимённым методом решения СЛАУ.

При завершении итерации, точка, полученная на последнем шаге этой итерации, берётся в качестве следующего приближения:

x→k+1=x→nk+1{\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{n}^{k+1}}.

Процедура продолжается до тех пор, пока не будет достигнута заданная точность ε{\displaystyle \varepsilon }, то есть пока:

||x→k+1−x→k||<ε{\displaystyle ||{\vec {x}}_{k+1}-{\vec {x}}_{k}||<\varepsilon }.

Улучшением данного метода является метод покоординатного спуска Гаусса — Зейделя.

Примечания

Литература

• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

См. также

Метод Гаусса (численное интегрирование) — Википедия

Материал из Википедии — свободной энциклопедии

Численное интегрирование функции x5+6×2+1{\displaystyle x^{5}+6x^{2}+1} методом гаусса-3

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

Например, для двух узлов можно получить метод 3-го порядка точности

I≈b−a2(f(a+b2−b−a23)+f(a+b2+b−a23)),{\displaystyle I\approx {\frac {b-a}{2}}\left(f\left({\frac {a+b}{2}}-{\frac {b-a}{2{\sqrt {3}}}}\right)+f\left({\frac {a+b}{2}}+{\frac {b-a}{2{\sqrt {3}}}}\right)\right)\,,}

тогда как для равноотстоящих узлов метода выше 2-го порядка получить невозможно. В общем случае, используя n{\displaystyle n} точек, можно получить метод с порядком точности 2n−1{\displaystyle 2n-1}. Значения узлов метода Гаусса по n{\displaystyle n} точкам являются корнями полинома Лежандра степени n{\displaystyle n}. Значения весов вычисляются по формуле ai=2(1−xi2)[Pn′(xi)]2{\displaystyle a_{i}={\frac {2}{(1-x_{i}^{2})\,[P_{n}'(x_{i})]^{2}}}}, где Pn′{\displaystyle P_{n}’} — первая производная полинома Лежандра.

Для n=3{\displaystyle n=3} узлы и веса имеют следующие значения : x1,3=±0.6,x2=0,{\displaystyle x_{1,3}=\pm {\sqrt {0.6}},x_{2}=0,} веса : a1,3=59,a2=89{\displaystyle a_{1,3}={\frac {5}{9}},a_{2}={\frac {8}{9}}}.

(Полином определен на отрезке [−1,1]{\displaystyle [-1,1]}).

Наиболее известен метод Гаусса по пяти точкам.

Метод Гаусса — Кронрода

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

I≈∑i=1naif(xi)+∑i=1n+1bif(yi){\displaystyle I\approx \sum _{i=1}^{n}a_{i}\,f(x_{i})+\sum _{i=1}^{n+1}b_{i}\,f(y_{i})},

где xi{\displaystyle x_{i}} — узлы метода Гаусса по n{\displaystyle n} точкам, а 3n+2{\displaystyle 3n+2} параметров ai{\displaystyle a_{i}}, bi{\displaystyle b_{i}}, yi{\displaystyle y_{i}} подобраны таким образом, чтобы порядок точности метода был равен 3n+1{\displaystyle 3n+1}. Тогда для оценки погрешности можно использовать эмпирическую формулу:

Δ=(200|I−IG|)1.5{\displaystyle \Delta =\left(200|I-I_{G}|\right)^{1.5}},

где IG{\displaystyle I_{G}} — приближённое значение интеграла, полученное методом Гаусса по n{\displaystyle n} точкам. Библиотеки gsl и SLATEC для вычисления определённых интегралов содержат подпрограммы, использующие метод Гаусса — Кронрода по 15, 21, 31, 41, 51 и 61 точкам.

См. также

Литература

1. Болтачев Г.Ш. Численные методы в теплофизике. Курс лекций Лекция 3: Численное интегрирование

Обсуждение:Метод Гаусса Википедия

Метод Гаусса

Метод Гаусса — это более общее понятие, чем метод решения СЛАУ. Например, существуют метод Гаусса вычисления определителя, метод Гаусса вычисления ранга матрицы. В общем случае метод Гаусса таков: 1) Выделить тип матрицы, для которой задача решается достаточно просто 2) Выделить тип преобразований, которые либо не меняют решения задачи, либо меняют его контролируемым образом 3) Произвольная матрица выделенными преобразованиями приводится к выделенному виду, тем самым задача сводится к более простой. — Эта реплика добавлена участником Goryachev (о • в)

А разве когда говорят о методе Гаусса в 1) бывает что-то кроме ступенчатого вида матрицы, а в 2) — что-то кроме элементарных преобразований строк (или столбцов, как непопулярный вариант)? Я думаю нет, поэтому давайте сделаем чуть попроще чем вы предлагаете — предподнесём метод Гаусса как в первую очередь метод приведения матрицы к ступенчатому виду с помощью элементарных преобразований. А дальше приведём приложения: ступенчатая форма может быть использована для решения СЛАУ (процедурой обратной подстановки), для нахождения детерминанта (если дополнительно считать число перестановок строк), ранга (= число ненулевых строк), LU-разложения (элементы матрицы L — это числа, на которые домножаются строки перед добавлением к другой строке, или что-то подобное). — X7q 18:33, 31 декабря 2009 (UTC)

1) Ну во-первых бывает(для вычисления определителя — треугольная матрица). Во-вторых, метод Гаусса — это выше изложенные общие принципы, конкретная реализация зависит от задачи. 2) Метод Гаусса — это элементарные преобразования? Смеетесь? Нет, давайте не будем его преподносить, как то, чем он не является. Метод приведения матрицы к ступенчатому виду — это теорема об основном процессе, только теоретическая база для одного пункта метода Гаусса, точнее, реализаций метода Гаусса для конкретных задач. И кстати, допустимые преобразования различны для разных задач. Goryachev 21:34, 1 января 2010 (UTC)

Треугольная матрица — частный вид ступенчатой. — X7q 21:51, 1 января 2010 (UTC)

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

Про «выше изложенные общие принципы» — вы можете привести авторитетный источник в котором были бы изложены эти общие принципы? Википедия — не место для оригинальных исследований, и если эти принципы нигде больше не упоминаются, то в ВП им тоже не место. — X7q 21:51, 1 января 2010 (UTC)

Конечно могу. Все тот же учебник по линейной алгебре Г. Д. Ким. Все, что я говорю, я прочитал в учебниках, и от себя ничего не добавляю. Goryachev 14:47, 2 января 2010 (UTC)

Мне кажется, что статью либо нужно переименовать в «Метод Гаусса(СЛАУ)», либо переписать, чтобы в ней содержались эти общие принципы и основные примеры(решение СЛАУ, вычисление определителя, вычисление ранга). — Эта реплика добавлена участником Goryachev (о • в)

А еще примеры есть? — X7q 18:33, 31 декабря 2009 (UTC)

Я не сталкивался с другими применениями. Goryachev 21:34, 1 января 2010 (UTC)

Про определитель и ранг можно просто сделать по одному подразделу. Про определитель сказать, на что он умножается после каждого элементарного преобразования (вследствие свойств определителей). Про ранг — сказать/доказать, что row space матрицы не меняется от элементарных преобразования строк, а размерность row space матрицы в ступенчатой форме (почти) очевидно равна числу ненулевых строк. — X7q 18:33, 31 декабря 2009 (UTC)

Вычисления определителя, ранга, решение СЛАУ — равноправные применения метода Гаусса, и нельзя выделять один над другими(как это в статье). При вычислении ранга допустимы не только преобразования строк, но и столбцов. Вообще, при вычислении ранга — наибольшая свобода с преобразованиями. Что за row space? И не размерность матрицы, а ранг 🙂 Goryachev 21:34, 1 января 2010 (UTC)

Про равноправные не согласен. Всё же, он наиболее известен именно как метод решения СЛАУ. — X7q 21:51, 1 января 2010 (UTC)

Ну это он Вам наиболее известен, как метод решения СЛАУ. Goryachev 14:47, 2 января 2010 (UTC)

Row space — пространство всех линейных комбинаций строк матрицы. Ранг матрицы (а точнее row rank, но он равен column rank ввиду какой-то теоремы, поэтому просто ранг) = размерность row space. — X7q 21:51, 1 января 2010 (UTC)

Понятно. Ввиду теоремы о базисном миноре. Goryachev 14:47, 2 января 2010 (UTC)

Пожалуйста проверьте в секции «Описание метода» индексы переменных. Мне кажется, что там должен быть вид a1j{\displaystyle a_{1j}} и xj{\displaystyle x_{j}}, а не a1j1{\displaystyle a_{1j_{1}}} и xj1{\displaystyle x_{j_{1}}} LeX 18:04, 3 января 2010 (UTC)

Изначально автор, видимо, предполагал все-таки трапецевидную форму основной матрицы, а для этого необходима перестановка столбцов, т.е. перенумерация переменных. Так что там все правильно. Вообще статья написана очень скверно, с ошибками. Ее бы переписать. Goryachev 10:57, 4 января 2010 (UTC)

Пример

ошибка у вас в статье а примере.. пересчитайте пожалуйста — Эта реплика добавлена с IP 89.23.18.112 (о)

исходя из примера, написанного в статье 2Х*1 + 3Х = о. Перепишите 78.128.195.83 22:02, 9 ноября 2010 (UTC)

Всё правильно в примере. Матлабом даже пересчитал. Единственное замечание — по-моему выбрана нестандартная последовательность элементарных операций. Обычно делается так: к строчке, в которой обнуляется коэффициент при старшем члене, прибавляется строчка, с помощью которой мы обнуляем, умноженная на что-то там. — X7q 22:38, 9 ноября 2010 (UTC)

Исправил. — X7q 22:53, 9 ноября 2010 (UTC)

спасибо, все сошлось 78.128.195.83 20:14, 13 ноября 2010 (UTC)

Сообщение об ошибке

Рисунок изображающий алгоритм решения не совсем корректен. В конце, вместо строки x[i] -= a[i][c+1] * x[c+1] / a[i][i], должен быть цикл по c (c=i; c<n-1; c=c+1) и уже внутри цикла — вышеприведенная строка. К сожалению я не обладаю необходимой квалификацией, чтобы данную ошибку самостоятельно. Прошу более опытных товарищей.

Автор сообщения: YaYauhen 06:45, 22 октября 2013 (UTC)

К обсуждению это надо перерисовывать рисунок, так что суть лучше будет на странице обсуждения. MPI3 11:25, 23 октября 2013 (UTC)

Может, тогда стоит вообще убрать картинку, пока её не исправят? Чтобы не смущать никого. 62.76.92.6 11:30, 21 мая 2014 (UTC)

Метод Гаусса (оптимизация) — Википедия. Что такое Метод Гаусса (оптимизация)

Материал из Википедии — свободной энциклопедии

Метод Гаусса^[1] — прямой метод решения задач многомерной оптимизации.

Описание

Пусть необходимо найти минимум действительнозначной функции f(x→)→minx→∈Rn{\displaystyle f({\vec {x}})\to \min _{{\vec {x}}\in \mathbb {R} ^{n}}}, а x→0{\displaystyle {\vec {x}}_{0}} — начальное приближение.

Суть метода заключается в том, чтобы на каждой итерации по очереди минимизировать функцию вдоль каждой из координат, то есть:

x→0k+1=x→k{\displaystyle {\vec {x}}_{0}^{k+1}={\vec {x}}_{k}}

{x→1k+1=x→0k+1+λ1e→1,λ1=arg⁡minλf(x→0k+1+λ1e→1)…x→nk+1=x→n−1k+1+λne→n,λn=arg⁡minλf(x→n−1k+1+λne→n){\displaystyle \left\{{\begin{array}{rl}{\vec {x}}_{1}^{k+1}={\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1},&\lambda _{1}=\arg \min _{\lambda }f({\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1})\\\ldots &\\{\vec {x}}_{n}^{k+1}={\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n},&\lambda _{n}=\arg \min _{\lambda }f({\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n})\end{array}}\right.},

где e→1,…,e→n{\displaystyle {\vec {e}}_{1},\ldots ,{\vec {e}}_{n}} — ортонормированный базис в рассматриваемом пространстве.

Таким образом метод как бы «поднимется» по координатам, используя на шагах одной итерации для вычисления следующей координаты точки приближения все предыдущие значения координат, вычисленные на той же итерации, в этом и состоит схожесть с одноимённым методом решения СЛАУ.

При завершении итерации, точка, полученная на последнем шаге этой итерации, берётся в качестве следующего приближения:

x→k+1=x→nk+1{\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{n}^{k+1}}.

Процедура продолжается до тех пор, пока не будет достигнута заданная точность ε{\displaystyle \varepsilon }, то есть пока:

||x→k+1−x→k||<ε{\displaystyle ||{\vec {x}}_{k+1}-{\vec {x}}_{k}||<\varepsilon }.

Улучшением данного метода является метод покоординатного спуска Гаусса — Зейделя.

Примечания

Литература

• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

См. также

Метод Гаусса (оптимизация) — Википедия. Что такое Метод Гаусса (оптимизация)

Материал из Википедии — свободной энциклопедии

Метод Гаусса^[1] — прямой метод решения задач многомерной оптимизации.

Описание

Пусть необходимо найти минимум действительнозначной функции f(x→)→minx→∈Rn{\displaystyle f({\vec {x}})\to \min _{{\vec {x}}\in \mathbb {R} ^{n}}}, а x→0{\displaystyle {\vec {x}}_{0}} — начальное приближение.

Суть метода заключается в том, чтобы на каждой итерации по очереди минимизировать функцию вдоль каждой из координат, то есть:

x→0k+1=x→k{\displaystyle {\vec {x}}_{0}^{k+1}={\vec {x}}_{k}}

{x→1k+1=x→0k+1+λ1e→1,λ1=arg⁡minλf(x→0k+1+λ1e→1)…x→nk+1=x→n−1k+1+λne→n,λn=arg⁡minλf(x→n−1k+1+λne→n){\displaystyle \left\{{\begin{array}{rl}{\vec {x}}_{1}^{k+1}={\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1},&\lambda _{1}=\arg \min _{\lambda }f({\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1})\\\ldots &\\{\vec {x}}_{n}^{k+1}={\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n},&\lambda _{n}=\arg \min _{\lambda }f({\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n})\end{array}}\right.},

где e→1,…,e→n{\displaystyle {\vec {e}}_{1},\ldots ,{\vec {e}}_{n}} — ортонормированный базис в рассматриваемом пространстве.

Таким образом метод как бы «поднимется» по координатам, используя на шагах одной итерации для вычисления следующей координаты точки приближения все предыдущие значения координат, вычисленные на той же итерации, в этом и состоит схожесть с одноимённым методом решения СЛАУ.

При завершении итерации, точка, полученная на последнем шаге этой итерации, берётся в качестве следующего приближения:

x→k+1=x→nk+1{\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{n}^{k+1}}.

Процедура продолжается до тех пор, пока не будет достигнута заданная точность ε{\displaystyle \varepsilon }, то есть пока:

||x→k+1−x→k||<ε{\displaystyle ||{\vec {x}}_{k+1}-{\vec {x}}_{k}||<\varepsilon }.

Улучшением данного метода является метод покоординатного спуска Гаусса — Зейделя.

Примечания

Литература

• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

См. также