Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
meraxujiep
41 / 41 / 4
Регистрация: 31.01.2013
Сообщений: 148
#1

Поиск универсального алгоритма LU разложения - C++

07.04.2013, 10:59. Просмотров 2100. Ответов 10
Метки нет (Все метки)

Реализовал LU разложение методом Гаусса, но тестируя приложение вылезло условие при котором этот алгоритм не действует, потом вспомнил что и в теории по линейной алгебре такое было, элемент матрицы а11!=0. На форуме много кодов для UL-разложения, но у них такая же проблема.
По форуму посмотрел, но не нашел решения проблемы.
Нужна теория по LU разложению, может есть универсальный алгоритм?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.04.2013, 10:59     Поиск универсального алгоритма LU разложения
Посмотрите здесь:
Реализация алгоритма А* (поиск кратчайших расстояний на графе) C++
C++ Задача на поиск алгоритма оптимального разбития набора фильмов с учетом оценок этих фильмов
алгоритм разложения функции C++
Разложения числа на цифры C++
Разложения ряда Тейлора C++
Вычисление функции с использованием разложения в ряд C++
C++ НОД n чисел путем канонического разложения
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iifat
2218 / 1371 / 101
Регистрация: 05.06.2011
Сообщений: 3,770
07.04.2013, 12:29     Поиск универсального алгоритма LU разложения #2
В алгоритмах и ищи. Есть метод Гаусса с выбором главного элемента, думаю, и LU-разложение должно быть с аналогичной модификацией.
meraxujiep
41 / 41 / 4
Регистрация: 31.01.2013
Сообщений: 148
07.04.2013, 15:20  [ТС]     Поиск универсального алгоритма LU разложения #3
Прочитал про метод Гаусса с выбором главного элемента, и понял что начал сам реализовывать такой ход( когда решал проблему). Повторно читать и углубляться не стал, начал делать как казалось мне правильно.
Вот что вышло.
В тетрадке сделал LU-разложение для матриц 3х3 и 4х4, сошлось.
Как бы удостоверится в правильности алгоритма?
функци LU-разложения:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void LU_decomposition(double **PointU, double **PointL, int size)
{
 for(int i=0;i<size;i++)
  {
   if(PointU[i][i]==0)
    {
     int max;
     double mass1;
     for(int st=i+1;st<size;st++)
     {
      if(PointU[st][i]!=0)
      {
       max=st;
       break;
      }
     }
       for(int o=0;o<size;o++)
        {
         mass1=PointU[i][o];
         PointU[i][o]=PointU[max][o];
         PointU[max][o]=mass1;
        }
 
    }
   for(int j=i+1;j<size;j++)
    {
     double m;
     m=PointU[j][i]/PointU[i][i];
     PointL[j][i]=m;
     for(int k=0;k<size;k++)
      {
       PointU[j][k]=PointU[j][k]-PointU[i][k]*m;
      }
    }
  }
}
palva
2561 / 1783 / 251
Регистрация: 08.06.2007
Сообщений: 6,910
Записей в блоге: 4
07.04.2013, 15:47     Поиск универсального алгоритма LU разложения #4
Обычно ищут максимальный по модулю элемент. Вы же находите первый не нулевой. Если он окажется очень близок к нулю, то теория предсказывает неприятности.

Информацию о перестановке строк вы не запоминаете? Тогда какая ценность этого алгоритма?

Надеюсь, вы понимаете что делаете, когда объявляете параметр double **PointU и в курсе, куда на самом деле обратится программа, когда увидит PointU[i][i] То, как вы размещаете матрицы в памяти довольно странно.
meraxujiep
41 / 41 / 4
Регистрация: 31.01.2013
Сообщений: 148
07.04.2013, 16:08  [ТС]     Поиск универсального алгоритма LU разложения #5
Цитата Сообщение от palva Посмотреть сообщение
Обычно ищут максимальный по модулю элемент. Вы же находите первый не нулевой. Если он окажется очень близок к нулю, то теория предсказывает неприятности.
Согласен, промах.

Цитата Сообщение от palva Посмотреть сообщение
Информацию о перестановке строк вы не запоминаете? Тогда какая ценность этого алгоритма?
Задача стоит сделать LU-разложение матрицы. По итогу получаю **PointU на верхнюю треугольную матрицу и **PointL на нижнюю треугольную матрицу с единичками на диагонали. Как мне кажется этот кусок можно использовать для нахождения определителя например, или для решения СЛУ(это собираюсь попробовать реализовать).


Цитата Сообщение от palva Посмотреть сообщение
Надеюсь, вы понимаете что делаете, когда объявляете параметр double **PointU и в курсе, куда на самом деле обратится программа, когда увидит PointU[i][i] То, как вы размещаете матрицы в памяти довольно странно.
Не понял что вы имели ввиду в этой части.
palva
2561 / 1783 / 251
Регистрация: 08.06.2007
Сообщений: 6,910
Записей в блоге: 4
07.04.2013, 16:32     Поиск универсального алгоритма LU разложения #6
2. Например для определителя. Вам нужно знать сколько раз вы переставляли строки, иначе вы рискуете получить неправильный знак определителя. А если для решения системы, то после решения двух треугольных систем придется точно также переставлять компоненты решения, как вы переставляли строки. Я к тому, что информацию о перестановках нужно выводить в качестве выходного параметра.

3. Мне не нравится как в функции у вас объявлены параметры. В каком виде вы задаете матрицу? Вот такая программа у меня даже не компилируется. Если я раскомментирую преобразование типов, то компиляция проходит, но при работе падает.
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int a[3][3]={1,2,3,4,5,6,7,8,9};
 
void f(int **a) {cout << a[2][2] << endl;}
 
int main() {
    cout << a[2][2] << endl;
    f( /*(int **) */ a);
    return 0;
}
Добавлено через 6 минут
Вы с перестановками компонент решения пока не возитесь. Решение системы находить от вас пока не требуют. Но формируйте целый массив на i-м месте которого будет стоять номер строки, с которой переставлялась i-я строка на i-м шаге. Если перестановки на самом деле не было, то ставьте номер i. Этот вектор пригодится, если придется решать систему.
meraxujiep
41 / 41 / 4
Регистрация: 31.01.2013
Сообщений: 148
07.04.2013, 18:10  [ТС]     Поиск универсального алгоритма LU разложения #7
Не создавался счетчик перестановок или вектор, про который вы говорили, или что-то подобное по той причине что это не требовалось.

Задаю матрицу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
double **PointU=new double*[size];
for(int i=0;i<size;i++)
PointU[i]=new double[size];
 
double **PointL=new double*[size];
for(int i=0;i<size;i++)
{
 PointL[i]=new double[size];
 for(int g=0;g<size;g++)
 {
  if(g==i)PointL[i][g]=1;
  else PointL[i][g]=0;
 }
}
затем вызываю функцию для заполнения матрицы vvod(PointU,size); приложение работает напрямую с массивами. как то так.
palva
2561 / 1783 / 251
Регистрация: 08.06.2007
Сообщений: 6,910
Записей в блоге: 4
07.04.2013, 18:29     Поиск универсального алгоритма LU разложения #8
Теперь с матрицей понятно. По-моему, все корректно. Хотя мало кто хранит матрицы в таком виде и говорить об универсальной программе вряд ли возможно, не говоря уже о том, что к программе проблемно обратиться из других языков, например из бейсика или фортрана.
Цитата Сообщение от meraxujiep Посмотреть сообщение
Не создавался счетчик перестановок или вектор, про который вы говорили, или что-то подобное по той причине что это не требовалось.
А что от вас требовалось? Разложить матрицу. Разложить ее невозможно. Такая уж матрица. Так пусть тогда программа вернет признак невозможности и дело с концом. Но вы занялись перестановкой строк, то есть разложили немного другую матрицу. Это логично. А вот какую матрицу вы на самом деле разложили - без вектора непонятно, строки же можно переставлять различным образом. Воспользоваться этим разложением для вычисления определителя или решения системы невозможно. Поэтому я и начал с того, что засомневался в ценности этого алгоритма.
meraxujiep
41 / 41 / 4
Регистрация: 31.01.2013
Сообщений: 148
07.04.2013, 19:06  [ТС]     Поиск универсального алгоритма LU разложения #9
Цитата Сообщение от palva Посмотреть сообщение
Хотя мало кто хранит матрицы в таком виде
На что фантазии и навыков хватило: ), другого не знаю.

Цитата Сообщение от palva Посмотреть сообщение
А что от вас требовалось?
Никто ничего не требовал, вспомнил что учил 1 семестр С++, захотелось сделать пару приложений по линейной алгебре. Хотел сделать разложение. На этом сайте раскладываются все матрицы в которых у меня вылезала ошибка http://www.kontrolnaya-rabota.ru/s/m...lu-raslogenie/, вот и начал копать чтоб и у меня все робило, не ознакомившись с теорией.
iifat
2218 / 1371 / 101
Регистрация: 05.06.2011
Сообщений: 3,770
08.04.2013, 05:10     Поиск универсального алгоритма LU разложения #10
Как я понимаю, применяя выбор главного элемента, мы получаем уже не LU-разложение, а L, U, и ещё перестановки строк/столбцов, что эквивалентно умножению на соответствующие матрицы достаточно простого вида, лень вспоминать точно. Этот метод вполне можно использовать для нахождения обратной матрицы и решения уравнений, но, таки повторюсь, это -- не совсем LU-разложение. И, конечно, нельзя просто переставить строки и забыть об том -- иначе это уж ни в какие ворота не полезет...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2015, 21:27     Поиск универсального алгоритма LU разложения
Еще ссылки по теме:
C++ Численно убедиться в справедливости разложения функции
C++ СЛУ методом LDLT разложения Холецкого
Метод вращений с построением КЮЭР-разложения C++
Вычисление функции с использованием их разложения в ряд C++
C++ Разложения функции в ряд Тейлора sin^3(x)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Exclusive048
0 / 0 / 0
Регистрация: 09.07.2015
Сообщений: 34
08.11.2015, 21:27     Поиск универсального алгоритма LU разложения #11
А можно взглянуть на весь код целиком. Метод Гаусса с выбором элемента и LU-разложения
Yandex
Объявления
08.11.2015, 21:27     Поиск универсального алгоритма LU разложения
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru