Show that norm is reduced in each iteration for weighted additive orthogonal projection

19 Views Asked by At

I'm stuck in the following problem from Saad's Iterative Methods for Sparse Linear Systems:

In an additive projection procedure, the $k+1$th residual vector is

$$\vec{r}_{k+1} = \sum_{i=1}^p w_i (I-P_i)\vec{r}_k$$

If the weights satisfy:

$$\sum_{i=1}^p w_i = 1 \ \ \ \ \ |w_i| \leq 1 \ \ \ \ \forall i$$

and the $I-P_i$ are orthogonal projectors, show that

$$||\vec{r}_{k+1}||_2 \leq ||\vec{r}_k||_2$$.

What I tried to do was just use the triangle inequality to obtain

$$||\vec{r}_{k+1}||_2^2 \leq \sum_{i=1}^p w_i^2||(I-P_i)\vec{r}_k ||_2^2 = \sum_{i=1}^p w_i^2 (||\vec{r}_k||_2^2 - ||P_i\vec{r}_k||_2^2) \leq \sum_{i=1}^p w_i^2||\vec{r}_k||_2^2$$

Where the equality holds due to $(I-P_i)$ being an orthogonal projector.

My problem is that, from where I am now, it would be easy if the weights were a convex combination, but in this case they are an affine combination with the extra restriction that $|w_i| \leq 1$, and I don't know how to continue from here.

Thank you!