当前位置：文档之家 › 矩阵doolittle分解算法

矩阵doolittle分解算法

  • 格式：doc
  • 大小：83.50 KB
  • 文档页数：6

解线性方程组的Doolittle分解
目的意义：
1.学习和掌握线性代数方程组的Doolittle分解法。
2.运用Doolittle分解法进行计算。

方法原理：
n阶线性方程组的系数矩阵A非奇异且有分解式A=LR，其中L为单位下三角矩阵，R为上
三角矩阵，即L=(lij),当ij时，rij=0，矩阵A的这种分解方法
为Doolittle的分解。




nnnnnnnnnnnnrrrrrrlllaaaaaaaaa22211211212121
22221
11211

1
1

1

比较等号两边的第i行和第j列的元素，可知nkkjikijrla1，因为
0,11,ijjjiniirrll
，所以nkkjikijrla1=ijkjikikrrl11，i<=j，从而

.,1,,11niijrlar
ikkjikijij

当niij,2,1时，

iijiikikkjjkkjjkijrlrlrla111，从而nijrrlaliiikkijkjiji
,,1,/)(
11

，于是就得

到了计算LR分解的一般计算公式。
算法描述：

Setp1：利用for循环求出11kkikikppipralr，11()/kikikippkkkplalrr。
Step2：11iiiikkkybly,得出1()/niiikkiikixyrxr
程序代码：
头文件：
#include
typedef double Datatype;
class Matrix
{
private:
Datatype **ar;
int M;
int N;
public:
Matrix(int a=0,int b=0);
~Matrix();
void print();
void Init();
void Doolittle(Matrix &L,Matrix &R);
friend void Init_LR(Matrix &L,Matrix &R);
void get_Y(Matrix &b,Matrix &L);
void get_X(Matrix &Y,Matrix &R);
};
CPP文件：
#include
#include
#include
#include"Doolittle.h"

void Init_LR(Matrix &L,Matrix &R)
{
for(int i=0;i{
for(int j=0;j{
if(i<=j)
{
if(i!=j)
{
L.ar[i][j]=0;
}
else
{
L.ar[i][j]=1;
}
}
else
{
R.ar[i][j]=0;
}
}
}
}
Matrix::Matrix(int a,int b)///////////////////构造函数
{
M=a;
N=b;
ar=(Datatype **)malloc(sizeof(Datatype *)*M);
for(int i=0;i{
ar[i]=(Datatype *)malloc(sizeof(Datatype)*N);
}
}

Matrix::~Matrix()////////////////////////////析构函数
{
for(int i=0;i{
free(ar[i]);
}
free(ar);
}

void Matrix::print()////////////////////////打印函数
{
for(int i=0;i{
for(int j=0;j{
cout<}
cout<}
}

void Matrix::Init()/////////////////////////初始化函数
{
for(int i=0;i{
cout<<"input the data of "<for(int j=0;j{
cin>>ar[i][j];
}
}
}
void Matrix::Doolittle(Matrix &L,Matrix &R)//////////////LR分解函数
{
for(int i=0;i{
for(int j=i;j{
Datatype sum=0;
for(int k=0;k{
sum+=L.ar[i][k]*R.ar[k][j];
}
R.ar[i][j]=ar[i][j]-sum;
}
for(j=i+1;j{
Datatype sum=0;
for(int k=0;k{
sum+=L.ar[j][k]*R.ar[k][i];
}
L.ar[j][i]=(ar[j][i]-sum)/R.ar[i][i];
}
}
}

void Matrix::get_Y(Matrix &b,Matrix &L)//计算得到Y
{
for(int i=0;i{
Datatype sum=0;
for(int j=0;j{
sum+=L.ar[i][j]*ar[j][0];
}
ar[i][0]=b.ar[i][0]-sum;
}
}

void Matrix::get_X(Matrix &Y,Matrix &R)//计算得到X
{
for(int i=M-1;i>=0;--i)
{
Datatype sum=0;
for(int j=M-1;j>i;--j)
{
sum+=R.ar[i][j]*ar[j][0];
}
ar[i][0]=(Y.ar[i][0]-sum)/R.ar[i][i];
}
}
主程序：
#include"Doolittle.h"
void main()
{
int row;
cout<<"input row"<cin>>row;
Matrix A(row,row),L(row,row),R(row,row),Y(row,1),B(row,1),X(row,1);
cout<<"请输入矩阵A"<A.Init();
cout<<"请输入矩阵b"<B.Init();
Init_LR(L,R);
A.Doolittle(L,R);
cout<<"*******分解矩阵A得L为********"<L.print();
cout<<"*******分解矩阵A得R为********"<R.print();
Y.get_Y(B,L);
cout<<"*******求得Y为********"<Y.print();
X.get_X(Y,R);
cout<<"*******求得X为********"<X.print();
}

测试数据：

123
123
123

24326225xxxxxxxxx







测试结果：
参考文献：
[1]刑志栋，矩阵数值分析， 陕西： 陕西科学技术出版社， 2005。
[2]谭浩强，C语言程序设计，北京：清华大学出版社，2005。
[3]翁惠玉，c语言程序设计思想与方法，北京：人民邮电出版社，2008

合集下载

Guass列选主元消去法和三角分解法

Guass列选主元消去法和三角分解法

Guass列选主元消去法和三⾓分解法 最近数值计算学了Guass列主消元法和三⾓分解法解线性⽅程组，具体原理如下：1、Guass列选主元消去法对于AX =B1）、消元过程：将（A|B）进⾏变换为，其中是上三⾓矩阵。

即：k从1到n-1a、列选主元选取第k列中绝对值最⼤元素作为主元。

b、换⾏c、归⼀化d、消元2）、回代过程：由解出。

2、三⾓分解法（Doolittle分解）将A分解为如下形式由矩阵乘法原理a、计算U的第⼀⾏，再计算L的第⼀列b、设已求出U的1⾄r-1⾏，L的1⾄r-1列。

先计算U的第r⾏，再计算L的第r列。

a）计算U的r⾏b）计算L的r列C#代码： 代码说明：Guass列主消元法部分将计算出来的根仍然储存在增⼴矩阵的最后⼀列，⽽Doolittle分解，将分解后的结果也储存⾄原来的数组中，这样可以节约空间。

using System;using System.Windows.Forms;namespace Test{public partial class Form1 : Form{public Form1(){InitializeComponent();}private void Cannel_Button_Click(object sender, EventArgs e){this.textBox1.Clear();this.textBox2.Clear();this.textBox3.Clear();boBox1.SelectedIndex = -1;}public double[,] GetNum(string str, int n){string[] strnum = str.Split(' ');double[,] a = new double[n, n + 1];int k = 0;for (int i = 0; i < n; i++){for (int j = 0; j < strnum.Length / n; j++){a[i, j] = double.Parse((strnum[k]).ToString());k++;}}return a;}public void Gauss(double[,] a, int n){int i, j;SelectColE(a, n);for (i = n - 1; i >= 0; i--){for (j = i + 1; j < n; j++)a[i, n] -= a[i, j] * a[j, n];a[i, n] /= a[i, i];}}//选择列主元并进⾏消元public void SelectColE(double[,] a, int n){int i, j, k, maxRowE;double temp; //⽤于记录消元时的因数for (j = 0; j < n; j++){maxRowE = j;for (i = j; i < n; i++)if (System.Math.Abs(a[i, j]) > System.Math.Abs(a[maxRowE, j]))maxRowE = i;if (maxRowE != j)swapRow(a, j, maxRowE, n); //与最⼤主元所在⾏交换//消元for (i = j + 1; i < n; i++){temp = a[i, j] / a[j, j];for (k = j; k < n + 1; k++)a[i, k] -= a[j, k] * temp;}}return;}public void swapRow(double[,] a, int m, int maxRowE, int n){int k;double temp;for (k = m; k < n + 1; k++){temp = a[m, k];a[m, k] = a[maxRowE, k];a[maxRowE, k] = temp;}}public void Doolittle(double[,] a, int n){for (int i = 0; i < n; i++){if (i == 0){for (int j = i + 1; j < n; j++)a[j, 0] = a[j, 0] / a[0, 0];}else{double temp = 0, s = 0;for (int j = i; j < n; j++){for (int k = 0; k < i; k++){temp = temp + a[i, k] * a[k, j];}a[i, j] = a[i, j] - temp;}for (int j = i + 1; j < n; j++){for (int k = 0; k < i; k++){s = s + a[j, k] * a[k, i];}a[j, i] = (a[j, i] - s) / a[i, i];}}}}private void Exit_Button_Click(object sender, EventArgs e){this.Close();}private void Confirm_Button_Click(object sender, EventArgs e){if (this.textBox2.Text.Trim().ToString().Length == 0){this.textBox2.Text = this.textBox1.Text.Trim();}else{this.textBox2.Text = this.textBox2.Text + "\r\n" + this.textBox1.Text.Trim();}this.textBox1.Clear();}private void Calculate_Button_Click(object sender, EventArgs e){string str = this.textBox2.Text.Trim().ToString();string myString = str.Replace("\n", " ").Replace("\r", string.Empty);double[,] a = new double[this.textBox2.Lines.GetUpperBound(0) + 1, this.textBox2.Lines.GetUpperBound(0) + 2];a = GetNum(myString, this.textBox2.Lines.GetUpperBound(0) + 1);if (boBox1.Text == "Guass列主消元法"){Gauss(a, this.textBox2.Lines.GetUpperBound(0) + 1);for (int i = 0; i < this.textBox2.Lines.GetUpperBound(0) + 1; i++){this.textBox3.Text = this.textBox3.Text + "\r\nX" + (i + 1) + "=" + a[i, this.textBox2.Lines.GetUpperBound(0) + 1]; }}else if (boBox1.Text == "Doolittle三⾓分解法"){this.textBox3.Enabled = true;Doolittle(a, this.textBox2.Lines.GetUpperBound(0) + 1);bel3.Text = "分解后的结果：";this.textBox3.Clear();this.textBox3.Text += "L矩阵：\r\n";for (int i = 0; i < this.textBox2.Lines.GetUpperBound(0) + 1; i++) {for (int j = 0; j < this.textBox2.Lines.GetUpperBound(0) + 1; j++) {if (j < i){this.textBox3.Text += a[i, j].ToString() + "\t";}else if (i == j){this.textBox3.Text += "1\t";}else{this.textBox3.Text += "0\t";}}this.textBox3.Text += "\r\n";}this.textBox3.Text += "\r\nU矩阵：\r\n";for (int i = 0; i < this.textBox2.Lines.GetUpperBound(0) + 1; i++) {for (int j = 0; j < this.textBox2.Lines.GetUpperBound(0) + 1; j++) {if (j >= i){this.textBox3.Text += a[i, j].ToString() + "\t";}else{this.textBox3.Text += "0\t";}}this.textBox3.Text += "\r\n";}}}private void textBox1_KeyDown(object sender, KeyEventArgs e){if (e.KeyCode == Keys.Enter){if (this.textBox1.Text.Trim().ToString().Length == 0){Calculate_Button_Click(sender, e);}else{Confirm_Button_Click(sender, e);}}}private void button1_Click(object sender, EventArgs e){this.textBox2.Enabled = true;}}} 运⾏截图： ⾄此完毕。

gauss消元法和doolittle乘法运算次数

gauss消元法和doolittle乘法运算次数

《深入探讨高斯消元法和Doolittle分解的乘法运算次数》在数学和计算机科学领域，高斯消元法和Doolittle分解是两种常见的线性代数运算方法。

它们被广泛用于解决线性方程组和矩阵求逆等问题。

本文将从深度和广度的角度对这两种方法进行全面评估，并进一步探讨它们的乘法运算次数的比较。

1. 高斯消元法简介高斯消元法是一种用于解决线性方程组的方法，通过矩阵变换将其转化为上三角矩阵，从而求解方程组。

其基本思想是通过一系列的行变换，将系数矩阵变换为上三角矩阵，再通过回代求解出未知数的值。

在实际应用中，高斯消元法通常需要进行大量的乘法和加法运算，其乘法运算次数随矩阵的大小而增加。

2. Doolittle分解简介Doolittle分解是将一个矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积，这种分解方法可以简化矩阵的求逆和解线性方程组的计算。

与高斯消元法相比，Doolittle分解在某些情况下可以更加高效地解决线性方程组的问题，尤其是对于大型矩阵的计算。

其乘法运算次数与矩阵的大小和稀疏程度密切相关。

3. 乘法运算次数比较在实际应用中，我们常常需要比较高斯消元法和Doolittle分解的乘法运算次数，以确定哪种方法更适合特定的问题。

根据理论分析和实际测试，我们可以得出以下结论：- 对于小型矩阵，通常情况下高斯消元法的乘法运算次数略少于Doolittle分解。

- 对于大型矩阵，Doolittle分解的乘法运算次数通常比高斯消元法少很多，尤其是在矩阵稀疏的情况下。

- 对于需要多次求解的问题，Doolittle分解可以通过分解一次，多次使用的方式，进一步减少总体的乘法运算次数。

4. 个人观点和理解从个人观点来看，高斯消元法和Doolittle分解都是非常重要的线性代数运算方法，它们各有优劣。

在实际应用中，我们需要根据具体的问题特点来选择合适的方法。

对于小型矩阵或需一次性解决问题的情况，高斯消元法可能更加便捷；而对于大型矩阵或需要多次使用的情况，Doolittle分解可能更具优势。

5.3 矩阵的三角分解法

5.3 矩阵的三角分解法


8
解： (1)分解A LU，令 2 5 6 1 4 13 19 l 21 6 3 6 l31 0 1 l32 0 u11 0 1 u12 u22 u13 u23 u33
24
由A L( DLT ) 1 l 21 l31 ... l n1 1 l32 ... ln 2 1 ... ... lnn 1 1 d1 ... d1l21 d2 ... d1l31 d 2 l32 d3 ... ... ... ... d1 l n1 d 2 ln2 d 3 ln 3 dn


25
由 i j时aij = l ik d k l jk l ij d j , 知
k =1
j -1
L, D元素计算公式
lij =
aij lik d k l jk
k =1
j -1
dj
j -1
( j 1, 2, ,i 1)
2 d i =aii l ik d k ( i 1, 2, , n) k =1
y1 b1 i -1 y y b l i ij i j j 1
i 2, 3, , n
( i n 1, , 1)
7
或 用 Doolittle 分解法
例:用矩阵的直接三角分解法解方程组
5 6 x1 10 2 4 13 19 x 19 2 6 3 6 30 x3
27
d1 a11
改进平方根法解方程组
1. 分解计算A=LDLT ,
d1 a11 对于i 2, 3, ..., n j 1 c a cik l jk ij ij k 1 cij ( j 1, 2, ..., i 1) lij dj i 1 d i aii cik l ik k 1
计算方法_矩阵LU分解法

计算方法_矩阵LU分解法

clear all; ％A=LU矩阵三角分解法n=input（'输入方矩阵的维数: ’);for i=1:nfor j=1:nA（i,j）=input（’依次输入矩阵元素：’)；endend %输入一个n阶方形矩阵for j=1：nL(j,j）=1; ％Doolittle分解，L对角元素全为1 endfor j=1:nU（1,j）=A(1,j)；end ％U的第一行for i=2：nL(i，1)=A（i，1)/U(1,1）；end %L的第一列for k=2：nfor j=k:nsum1=0；for m=1：k-1sum1=sum1+L（k，m)＊U（m,j);end %求和U（k，j）=A（k,j）-sum1；endfor i=k+1：nsum2=0；for m=1:k-1sum2=sum2+L(i,m）*U（m,k)；end ％求和L(i,k)=(A（i，k)—sum2)/U（k，k)；endendL %输出下三角矩阵LU %输出上三角矩阵U运行结果：（示例）输入方矩阵的维数： 4依次输入矩阵元素： 1依次输入矩阵元素： 1依次输入矩阵元素: 2依次输入矩阵元素： 3依次输入矩阵元素: 0依次输入矩阵元素： 2依次输入矩阵元素： 1依次输入矩阵元素： 2依次输入矩阵元素： 1依次输入矩阵元素: —1依次输入矩阵元素： 2依次输入矩阵元素： 2依次输入矩阵元素: 2依次输入矩阵元素： 2依次输入矩阵元素: 5依次输入矩阵元素：9A=LU分解后则可以求解Ax=b线性方程组，相关计算参考计算方法，这里不再详细介绍。