计算课程讲义.doc

非线性方程组求解 [完毕日期09-8-20]
or whereand

迭代法
寻找一种数列 使得
●迭代步长 使得
●迭代终结 （收敛） 或者 超过最大迭代次数 （发散）
Algorithm
given 初始化 , > 0，最大迭代次数max
repeat
1. 计算 和 …或者
2. if , return .
3. 计算…或者
4.
until ＞max
牛顿迭代法 n=1

This is called the linearized equation.

n>1

其中

Unconstrained minimization无约束最优问题
convex diff
min , 其中

牛顿迭代法
其中

Algorithm
given 初始化 , > 0，最大迭代次数max
repeat
1. 计算 和
2. if , return .
3. 计算
4.
until ＞max

Equality constrained minimization等式约束最优问题
with ; convex diff

, .

min
subject to

牛顿迭代法
, .
步长为

当为可行性解（）

内点法(primal-dual interior-point methods)

,

KKT …
minimize
subject to
其中 convex diff ; with .

我们要解如下非线性方程组

因此
其中

The primal-dual search direction

线性方程组求解 [完毕日期09-8-21]

LU分解； Cholesky分解（）
i.e, QR分解
i.e, QR分解；Cholesky分解
Nonsingular matrix The LU factorization
Where P is an -permutation matrix, L is a unit lower triangular
-matrix ( a lower triangular matrix with diagonal elements equal to one),and U is nonsingular upper triangular -matrix.
Positive definite matrix The Cholesky factorization
where L is lower triangular with positive diagonal elements
matrix with zero nullspace The QR factorization
Where Q is -orthogonal matrix and R is an -upper triangular matrix with positive diagonal elements.

Triangular matrix：A matrix A is upper triangular if if 。A triangular matrix is called nonsingular if all the diagonal elements are nonzero. It is singular if one or more of the diagonal elements are zero.
Forward/Back substitution
A is a nonsingular lower triangular matrix of order n. are

解法

Flop count: 1+3+5+…+(2n-1)=n2 。

Forward/Back substitution (Recursive formulation)
then

The Cholesky factorization: Positive definite matrix
positive definite: A is symmetric and for all nonzero x.
,
where L is lower triangular with positive diagonal elements therefore
and is lower triangular with positive diagonal elements.
makes:

Therefore , , .
In fact, . So, , and that makes positive definite matrix.
Schur Complement (of positive definite matrix elementis positive definite)

whereis a nonzero n-1 vector then x is a nonzero n vector, so .

Therefore is positive definite matrix of order n-1.

Solving linear equations by Cholesky factorization
为了计算, 我们做Cholesky分解，需要解方程 .

Computing the inverse
计算 ，，…，。
To be continued…
喜乐旳心，乃是良药；忧伤旳灵，使骨枯干 (箴17:22)

祝小朋友们学习快乐。