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

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

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

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

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

Реализовал LU разложение методом Гаусса, но тестируя приложение вылезло условие при котором этот алгоритм не действует, потом вспомнил что и в теории по линейной алгебре такое было, элемент матрицы а11!=0. На форуме много кодов для UL-разложения, но у них такая же проблема.
По форуму посмотрел, но не нашел решения проблемы.
Нужна теория по LU разложению, может есть универсальный алгоритм?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.04.2013, 10:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск универсального алгоритма LU разложения (C++):

Поиск исходников алгоритма шифрования DES - C++
Друзья, подскажите где найти исходники алгоритма шифрования DES, желательно на Visual C++ без использования WinAPI, но если есть просто C++...

Реализация алгоритма А* (поиск кратчайших расстояний на графе) - C++
В общем, уже несколько дней бьюсь над небольшой проблемой: написал поиск кратчайших путей на графе на основе алгоритма А*. Пути...

Задача на поиск алгоритма оптимального разбития набора фильмов с учетом оценок этих фильмов - C++
К дедушке приехали внуки: Екатерина и Дмитрий. Дедушка подготовил им подарок - коробку с видеофильмами, но сказал, что в коробке четное...

Оптимизация (поиск количества всех способов разложения числа на нечетные слагаемые) - Pascal
Приветствую. Задание звучит следующим образом. Задано целое положительное число n. Требуется найти число способов представить его в...

Поиск алгоритма - Алгоритмы
Всем доброго времени суток. Можно-ли вычислить алгоритм последовательности чисел,к примеру 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0?Тоесть узнать...

Поиск максимума без алгоритма ветвления. - Pascal
Задача состоит в том, что нужно найти максимум и минимум двух натуральных чисел, не используя алгоритм ветвления. Намекните хотя бы на...

10
iifat
2270 / 1426 / 114
Регистрация: 05.06.2011
Сообщений: 3,910
07.04.2013, 12:29 #2
В алгоритмах и ищи. Есть метод Гаусса с выбором главного элемента, думаю, и LU-разложение должно быть с аналогичной модификацией.
1
meraxujiep
42 / 43 / 4
Регистрация: 31.01.2013
Сообщений: 150
07.04.2013, 15:20  [ТС] #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;
      }
    }
  }
}
0
palva
2754 / 1855 / 268
Регистрация: 08.06.2007
Сообщений: 7,088
Записей в блоге: 4
07.04.2013, 15:47 #4
Обычно ищут максимальный по модулю элемент. Вы же находите первый не нулевой. Если он окажется очень близок к нулю, то теория предсказывает неприятности.

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

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

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


Цитата Сообщение от palva Посмотреть сообщение
Надеюсь, вы понимаете что делаете, когда объявляете параметр double **PointU и в курсе, куда на самом деле обратится программа, когда увидит PointU[i][i] То, как вы размещаете матрицы в памяти довольно странно.
Не понял что вы имели ввиду в этой части.
0
palva
2754 / 1855 / 268
Регистрация: 08.06.2007
Сообщений: 7,088
Записей в блоге: 4
07.04.2013, 16:32 #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. Этот вектор пригодится, если придется решать систему.
0
meraxujiep
42 / 43 / 4
Регистрация: 31.01.2013
Сообщений: 150
07.04.2013, 18:10  [ТС] #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); приложение работает напрямую с массивами. как то так.
0
palva
2754 / 1855 / 268
Регистрация: 08.06.2007
Сообщений: 7,088
Записей в блоге: 4
07.04.2013, 18:29 #8
Теперь с матрицей понятно. По-моему, все корректно. Хотя мало кто хранит матрицы в таком виде и говорить об универсальной программе вряд ли возможно, не говоря уже о том, что к программе проблемно обратиться из других языков, например из бейсика или фортрана.
Цитата Сообщение от meraxujiep Посмотреть сообщение
Не создавался счетчик перестановок или вектор, про который вы говорили, или что-то подобное по той причине что это не требовалось.
А что от вас требовалось? Разложить матрицу. Разложить ее невозможно. Такая уж матрица. Так пусть тогда программа вернет признак невозможности и дело с концом. Но вы занялись перестановкой строк, то есть разложили немного другую матрицу. Это логично. А вот какую матрицу вы на самом деле разложили - без вектора непонятно, строки же можно переставлять различным образом. Воспользоваться этим разложением для вычисления определителя или решения системы невозможно. Поэтому я и начал с того, что засомневался в ценности этого алгоритма.
0
meraxujiep
42 / 43 / 4
Регистрация: 31.01.2013
Сообщений: 150
07.04.2013, 19:06  [ТС] #9
Цитата Сообщение от palva Посмотреть сообщение
Хотя мало кто хранит матрицы в таком виде
На что фантазии и навыков хватило: ), другого не знаю.

Цитата Сообщение от palva Посмотреть сообщение
А что от вас требовалось?
Никто ничего не требовал, вспомнил что учил 1 семестр С++, захотелось сделать пару приложений по линейной алгебре. Хотел сделать разложение. На этом сайте раскладываются все матрицы в которых у меня вылезала ошибка http://www.kontrolnaya-rabota.ru/s/matrix/lu-raslogenie/, вот и начал копать чтоб и у меня все робило, не ознакомившись с теорией.
0
iifat
2270 / 1426 / 114
Регистрация: 05.06.2011
Сообщений: 3,910
08.04.2013, 05:10 #10
Как я понимаю, применяя выбор главного элемента, мы получаем уже не LU-разложение, а L, U, и ещё перестановки строк/столбцов, что эквивалентно умножению на соответствующие матрицы достаточно простого вида, лень вспоминать точно. Этот метод вполне можно использовать для нахождения обратной матрицы и решения уравнений, но, таки повторюсь, это -- не совсем LU-разложение. И, конечно, нельзя просто переставить строки и забыть об том -- иначе это уж ни в какие ворота не полезет...
0
Exclusive048
0 / 0 / 0
Регистрация: 09.07.2015
Сообщений: 34
08.11.2015, 21:27 #11
А можно взглянуть на весь код целиком. Метод Гаусса с выбором элемента и LU-разложения
0
08.11.2015, 21:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2015, 21:27
Привет! Вот еще темы с ответами:

Поиск алгоритма нахождения наилучшего результата - Алгоритмы
Дано: N-ое кол-во таблиц. При объединении трех создается новая таблица (пример ниже) 1 1 1 1 + 1 1 1 0 + 1 0 0 0 = 2 1 1 1 1 0 1...

Поиск в случайном бинарном дереве. Оценка алгоритма - Алгоритмы
Здравствуйте! Подскажите пожалуйста, каким образом можно оценить этот алгоритм(поиск в рандомизированном бинарном дереве) в лучшем,среднем...

Сложность алгоритма, использующего поиск по регулярным выражениям - Perl
Необходимо найти вычислительную сложность алгоритма, в котором используется поиск по регулярным выражениям. Алгоритм примерно такой: ...

Обход xml дерева. поиск оптимального алгоритма - C#
Может кто-нибудь подсказать алгоритм с помощью которого можно сохранять treeView в xml, а также читать xml в treeview ?


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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