0 / 0 / 0
Регистрация: 24.03.2016
Сообщений: 4
|
|
1 | |
Метод Крамера или метод Гаусса. Реализация24.03.2016, 14:29. Показов 5751. Ответов 3
Метки нет (Все метки)
Доброго времени суток. Стоит задача написать метод Гаусса или метод Крамера для решения СЛАУ на lisp, как это сделать даже на уровне алгоритма, я не знаю. На вход подается матрица, нужно будет работать с большими матрицами, например 10 на 10. На Lisp никогда не приходилось кодить) Помогите, пожалуйста, очень срочно.
0
|
24.03.2016, 14:29 | |
Ответы с готовыми решениями:
3
Метод Гаусса или метод Крамера. Реализация СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя Метод Крамера и Гаусса для n неизвестных Метод Крамера или обратной матрцы! |
Модератор
|
|||||||||||
24.03.2016, 16:08 | 2 | ||||||||||
Основой метода Крамера является вычисление определителей. Вот один из способов:
А вот метод Гаусса:
3
|
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
24.03.2016, 23:44 | 3 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Сообщение было отмечено Catstail как решение
Решение
Лисп лиспом, но линейную алгебру надо знать!
Десять уравнений ― это маленькие системы. В численных методах счёт уравнений может идти на десятки и сотни тысяч. Но это отдельная наука, я плохо её знаю. Тем не менее, по Крамеру всё равно не хочется решать ничего выше второго порядка. Нерациональный он. Вообще, у систем может быть разное поведение. Они могут не иметь решения. Если у них есть решения, то либо ровно одно, либо бесконечно много. Во втором случае все решения можно получить, выразив так называемые главные неизвестные через свободные, и давая свободным произвольные значения. Какое API вы предполагаете для решения этих вопросов, трудно сказать. Мне кажется, имеет смысл написать две функции: приведение матрицы к ступенчатому виду и к «приведённому» ступенчатому виду (не припомню, как он по-русски, а по-английски ― reduced row echelon form). В частности, по приведённому ступенчатому виду расширенной матрицы системы невооружённым глазом видно решение системы. Неприведённый ступенчатый вид матрицы можно использовать и для других целей: вычисление ранга, например, или определителя, если при получении этого вида не используется умножение строк на число. Начнём программу на лиспе так:
Вообще, чтобы получить доступ к символу mysym из пакета mypackage, можно использовать префиксную запись mypackage::mysym. Пакет может экспортировать некоторые символы. Такие символы называются внешними, и в префиксной записи можно ставить одно двоеточие: mypackage:my-external-sym. Внешние символы можно рассматривать как API пакета. Когда вы видите в коде префикс с двойным двоеточием, это всегда подозрительно: почему пользуются неэспортированным символом? Не деталь ли это реализации, которая может измениться в следующем релизе? Если один пакет импортирует другой, то все внешние символы импортируемого пакета можно использовать без префиксов. Это простая, но удобная система. Мы импортируем пакет CL, чтобы можно было без префиксов использовать обычные лисповые функции и т. п. Экспортируем мы имена функций, представляющие ценность для внешнего мира. Это row-echelon и reduced-row-echelon, вычисляющие соответственно ступенчатую и приведённую ступенчатую формы, а также некоторые утилиты: число строк и столбцов матрицы и элементарные операции со столбцами. Потом мы пишем форму in-package, которая делает пакет GAUSS текущим. Обычно все формы defpackage собирают в отдельном файле, по традиции называемом package.lisp, а файлы с кодом начинают сразу строчкой in-package. Однако если вас интересует организация библиотек в виде файлов, лучше в отдельной теме обсудить. Пока и так сойдёт. Теперь переходим к коду. В лиспе есть многомерные массивы, поэтому, не мудрствуя, будем работать с двумерными массивами. Размеры многомерного массива можно достать функцией array-dimension. Раз мы работаем с матрицами, удобно завести функции row-dimension и column-dimension, возвращающие число строк и столбцов. Функции маленькие, поэтому заинлайним их (предварительная оптимизация, так сказать).
Мы имеем право применять три вида элементарных преобразований строк: перестановка двух строк, умножение строки на число, и прибавление к строке другой строки, умноженной на число. Нетрудно понять, что соответствующие операции для систем уравнений не влияют на множество решений (если только во втором случае не умножать на 0). Напишем функции, которые выполняют эти преобразования. Поскольку создавать на каждый чих новую матрицу накладно, мы будем преобразовывать матрицы in place, то есть изменять их сами. Чтобы не забывать, что функции изменяют свои аргументы (что для функций, вообще говоря, нетипично), мы в докстринг включим слово destructively. При этом функциям неплохо и возвращать что-нибудь. Договоримся, что они будут возвращать саму матрицу.
dotimes ― один из немудрёный операторов цикла в лиспе, который запускает счётчик всегда с нуля и перебирает указанное число значений счётчика. То есть dotimes i n эквивалентно for (i = 0; i < n; ++i). В лиспе есть обычай отовсюду возвращать значения, это очень удобно. По умолчанию dotimes возвращает неинтересное значение nil, но факультативный третий аргумент в шапке является выражением, которое нужно вернуть. Мы указываем вернуть a, то есть саму матрицу. Вообще, функция возвращает значение последней вычисленной формы. В наших функциях по одной форме ― dotimes; их значение и будет возвращено. Доступ к элементам массива осуществляется функцией aref: aref a i j эквивалентно a[i, j]. Когда мы меняем местами два элемента, мы можем использовать временную переменную для хранения одной из них. Вместо этого мы воспользуемся оператором параллельного присваивания psetf. Обычный оператор присваивания ― setf. incf эквивалентно +=. К сожалению, аналога *= нет, поэтому в multiply-row честно пишем выражение полностью. Каков алгоритм приведения матрицы к ступенчатому виду? Берём Я не в ударе, почитайте любой учебник линейной алгебры. Напишем вспомогательные функции. Сначала ― занулить все элементы под a[i,j]. Здесь нужно делать цикл по номерам строк от i+1 до числа строк. К сожалению, dotimes умеет только с нуля. Поэтому мы воспользуемся мудрёным макросом ― loop с ключевыми словами. Он представляет большие возможности ― например, больше, чем сишный for. На самом деле это специальный язык для циклов ― язык внутри языка, который надо учить отдельно. Он не без недостатков и не всем нравится, но часто удобен. Здесь мы используем его наподобие паскалевского for; однако, below означает, что счётчик принимает только значения, строго меньшие верхнего предела.
Заодно напишем зануление элементов над a[i,j], пригодится для обратного хода метода Гаусса. Его можно было бы сделать с помощью dotimes, но я просто подправил код предыдущей функции. В for нижний предел 0 можно не писать.
Сестра-близнец пригодится для обратного хода. (Вообще, мне начинает не нравиться дублирование кода.)
Мы используем следующие возможности цикла loop. Во-первых, with ... = вводит локальные переменные для цикла. Во-вторых, мы совмещаем одновременно делаем цикл типа while, и цикл по номерам строк с ненулевыми элементами. Дело в том, что клауза for может иметь вид типа for i from 1 to 10, а может иметь вид типа for i = выражение, в последнем случае на каждой итерации переменной i присваивается значение выражения. Тело цикла у нас разбито в два do. Сначала ― что делать, если нашли-таки строку с ненулевым элементом (я воспользовался лисповым оператором while, эквивалентным if с одной веткой, а можно было воспользоваться одноимённой клаузой loop); а во втором do ― увеличение текущего столбца, которое нужно делать при любом раскладе. Да, incf по умолчанию увеличивает на 1. Следующая функция выполняет обратный ход метода Гаусса в предположении, что аргумент уже в ступенчатом виде. Алгоритм простой: в каждой строке ищется ненулевой элемент и зануляются все элементы над ним. Здесь мы совмещаем два счётчика и цикл while (если в строке уже нет ненулевых элементов, нужно заканчивать).
Нетрудно понять, какое решение. Неопределённая система, № 690:
Кто немного знает линейную алгебру, понимает, что второе и четвёртое неизвестные ― свободные, они могут принимать любые значения, и общее решение имеет ви Из приведённой формы всё видно невооружённым глазом. У Проскурякова в ответе в качестве главных взяты x1 и x2. С его ответом можно сравнить, если эти столбцы записать последними в матрице системы. Несовместная система:
несовместность которой очевидна. Учите алгебру!
2
|
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
|
||||||
25.03.2016, 15:15 | 4 | |||||
Весь код из предыдущего сообщения:
В последнем докстринге надо убрать, конечно, without multiplying. Здесь пофикшено.
2
|
25.03.2016, 15:15 | |
25.03.2016, 15:15 | |
Помогаю со студенческими работами здесь
4
Переделать программу, использующую метод Гаусса в метод Барейса Базис или нет (метод Гаусса) Метод Гаусса-Зейделя,метод Якоби, LU разложения Метод итераций Якоби и метод Гаусса-Зейделя Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |