Preconditioning the Steepest Descent Method

[Deimantas]

Homework Statement

Homework Equations

P^k = A*X^k - F

τ_k = ((A*X^k - F)*(A*X^k - F))/(A*(A*X^k - F))*(A*X^k - F)

X^k+1 = X^k - τ_k * (A*X^k - F)

The Attempt at a Solution

We are given a system of equations:


AX=F, where A_3x3= (2 1 0.95; 1 2 1; 0.95 1 2) and F= (3.95;4;3.95)^τ

(The solution is (1;1;1)^τ)

We choose the first X freely: X⁰ = (0;0;0)^τ

Therefore:

(1) AX⁰-F = -F = (-3.95;-4;-3.95)^τ

(2) (A*X⁰ - F)*(A*X⁰ - F) = 47.205

(3) A*(A*X⁰ - F) = (-15.6525;-15.9;-15.6525)^τ

(4) (A*(A*X^k - F))*(A*X^k - F) = 187.25475

So τ₀ = 0.252090

Therefore our new approximate X is:

(5) X¹ = X⁰ - τ₀ * (A*X^k - F) = (0;0;0)^τ - 0.252090 * (-3.95;-4;-3.95)^τ ≈ (0.995754;1.008359;0.995754)^τ

We repeat this process with the new approximation of X, until we reach the desired accuracy.

This is the method of steepest descent without preconditioning. Can anyone show me how each step of this algorithm changes with preconditioning applied? Suppose we use a preconditioner matrix B which is equal to the inverse of A (or any matrix that you think would be the best).

I'd highly appreciate any help. I've made a program to calculate solutions of a system of equations using SDM already, and it works fine, I just don't understand how to apply preconditioning. Hopefully the equations I've written are readable, apologies.

 

[Ray Vickson]

Homework Statement

Homework Equations

P^k = A*X^k - F

τ_k = ((A*X^k - F)*(A*X^k - F))/(A*(A*X^k - F))*(A*X^k - F)

X^k+1 = X^k - τ_k * (A*X^k - F)

The Attempt at a Solution

We are given a system of equations:


AX=F, where A_3x3= (2 1 0.95; 1 2 1; 0.95 1 2) and F= (3.95;4;3.95)^τ

(The solution is (1;1;1)^τ)

We choose the first X freely: X⁰ = (0;0;0)^τ

Therefore:

(1) AX⁰-F = -F = (-3.95;-4;-3.95)^τ

(2) (A*X⁰ - F)*(A*X⁰ - F) = 47.205

(3) A*(A*X⁰ - F) = (-15.6525;-15.9;-15.6525)^τ

(4) (A*(A*X^k - F))*(A*X^k - F) = 187.25475

So τ₀ = 0.252090

Therefore our new approximate X is:

(5) X¹ = X⁰ - τ₀ * (A*X^k - F) = (0;0;0)^τ - 0.252090 * (-3.95;-4;-3.95)^τ ≈ (0.995754;1.008359;0.995754)^τ

We repeat this process with the new approximation of X, until we reach the desired accuracy.

This is the method of steepest descent without preconditioning. Can anyone show me how each step of this algorithm changes with preconditioning applied? Suppose we use a preconditioner matrix B which is equal to the inverse of A (or any matrix that you think would be the best).

I'd highly appreciate any help. I've made a program to calculate solutions of a system of equations using SDM already, and it works fine, I just don't understand how to apply preconditioning. Hopefully the equations I've written are readable, apologies.

The topic is a bit "large" to cover in a Forum like this one. An on-line search using keywords "steepest descent + precondioned" (or "preconditioning") yields many, many articles.