Talk:Gram–Schmidt process

From Wikipedia, the free encyclopedia

In the definition of the projection operator I changed <u, v> to denote the inner product instead of the dot product. The dot product is just a special case.

Maciej

Does anyone know when the Gram Schimdt process was discovered? And who Mr. Gram and Mr. Schmidt are?

Jørgen Pedersen Gram (1850-1916), Danish mathematician.

Sebastjan

I was going to rewrite the process in terms of projections to clean it up a bit, but I'll probably stuff it up somewhere and be shouted at. So, if you feel up to doing so, I think it'd clear up the process greatly. Dysprosia 01:41, 26 Aug 2004 (UTC)

I changed the calculation of u_2 etc. to use projection onto u_1 instead of onto e_1. This allows the process to work in fields where you cannot take square roots, such as the rationals. I have a program that produces a series of orthogonal vectors spanning the right space. norm@cap-lore.com .

Ewwwwww, I really don't like the notation proj_u v. If anything it should be written proj_v u, to emphasize that the projection is just a scaling of u.


Contents

[edit] Maybe we need an illustration

Maybe we need an illustration of the projection just like most text books.

I just created this…

…would it fulfill its purpose? –Gustavb 07:16, 18 February 2006 (UTC)
Yes, I guess that is basically it. However, I think that u2 is too long. We need to have
u_2 + \operatorname{proj}_{u_1}(v_2) = v_2,
so the direction of u2 is correct, but it should only go up to the dashed line. Does that make sense to you? If not, I'll change the picture myself, but I don't know the TeX package you are using (it looks quite easy to use though). -- Jitse Niesen (talk) 14:52, 18 February 2006 (UTC)
Yes, of course…guess I was tired when I did it. I have now created a new one but unfortunately I can't upload it due to a restriction in wikimedia commons which only allows users registered for more than four days to replace files (I registered yesterday.) –Gustavb 15:24, 18 February 2006 (UTC)
That seems rather silly to me; what's the purpose of prohibiting somebody from overwriting their own files? If you want, you can email it to me at my-first-name@ma.hw.ac.uk (making the obvious substitution) and I'll upload it on your behalf. You can also just wait a couple of days. -- Jitse Niesen (talk) 15:49, 18 February 2006 (UTC)
I don't think it checks who uploaded the original file – it just block all uploads for the purpose of reducing vandalism (I assume). So yes, it's a bad solution. Thanks for uploading the new version. –Gustavb 16:27, 18 February 2006 (UTC)

[edit] Basis

Does the set of vectors v1, …, vk not need to form a basis over the vector space? Tis is not mentioned anywhere on the page and is very important to the defintion I have learnt.Stb20 12:48, 22 January 2007 (UTC)

I'm rather sure that they don't need to form a basis. Do you have a text book which says that they do need to form a basis?
They do need to be linearly independent though. This is mentioned in the article. -- Jitse Niesen (talk) 11:35, 23 January 2007 (UTC)
My book does mention it yes, although it is refering to this process in forming an othogonal basis, rather than just an orthogonal set of vectors, so I assume this is the only time it applies. Is it still worth a mention? Stb20 11:47, 24 January 2007 (UTC)

[edit] Notation

for the projection, shouldn't it be proj(V) = [(V*U)/(U*U)] * U?? * is the dot product.

The author wrote it as (v,u)/(u, u) * u, which I don't understand what they mean.

<V,U> is a matrix or something else?

If it is a matrix then there shouldn't be division. If the expression is still correct, please explain what do the symbols mean.


Xfliang 05:40, 16 February 2007 (UTC)

<v,u> is another notation for the dot product of v and u. I added a bit to the article to explain this. -- Jitse Niesen (talk) 07:17, 16 February 2007 (UTC)

[edit] Factual accuracy on the method presented here

Maybe I'm reading the information on the page wrong, but as far as I can tell if I try and use the information here to create the 4th Legendre polynomial starting from 1,x,x^2,x^3 etc. I get an incorrect answer \left( x^4 - \frac 5 7 x^2 -\frac 1 5 \right), however if I use the information on Mathworld I get the right answer. Eraserhead1 23:31, 18 February 2007 (UTC)

I'm sorry, but I can't see where the algorithm on this page is different from the algorithm in MathWorld. Could you perhaps explain where the algorithms differ? Is P4 the first case where you get different results? -- Jitse Niesen (talk) 13:01, 10 March 2007 (UTC)

[edit] numerically stable algorithm

I think there"s a mistake in the superscripts in that section. In the last equation it should be either uk(k-1) OR on the right-hand side of the eqution all superscripts must be increased by one. Also the notation for the projection operator is a bit confusing: isn't actually meant projuk(k-1)uk(k-2) instead of proju(k-1)uk(k-2)? There seems to be a k missing... 134.60.1.151 12:31, 14 June 2007 (UTC)

Perhaps it's easier to write the algorithm as
\mathbf{u}_k^{(1)} = \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_k,
\mathbf{u}_k^{(2)} = \mathbf{u}_k^{(1)} - \mathrm{proj}_{\mathbf{u}_2^{(1)}} \, \mathbf{u}_k^{(1)},
\vdots
\mathbf{u}_k^{(k-2)} = \mathbf{u}_k^{(k-3)} - \mathrm{proj}_{\mathbf{u}_{k-2}^{(k-1)}} \, \mathbf{u}_k^{(k-3)},
\mathbf{u}_k^{(k-1)} = \mathbf{u}_k^{(k-2)} - \mathrm{proj}_{\mathbf{u}_{k-1}^{(k-2)}} \, \mathbf{u}_k^{(k-2)}.
The vectors \mathbf{u}_1, \mathbf{u}_2^{(1)}, \ldots, \mathbf{u}_k^{(k-1)} are then orthogonal. If you now use \mathbf{u}_k to denote the vector \mathbf{u}_k^{(k-1)} , you get the algorithm as mentioned in the article. Perhaps the notation isn't quite consistent, but I prefered to save some superscripts. Do you think the version with \mathbf{u}_k^{(k-1)} is less confusing?
Do you understand the difference between the original and the stabilized algorithm on an implementation level? There is pseudocode for the stabilized version in the article. The original version looks like
input: v1, …, vk; output: u1, …, uk
for j from 1 to k do
\mathbf{u}_j \leftarrow \mathbf{v}_j
for i from 1 to j − 1 do
\mathbf{u}_j \leftarrow \mathbf{u}_j - \langle \mathbf{v}_j, \mathbf{u}_i \rangle \mathbf{u}_i
end for
\mathbf{u}_j \leftarrow \frac{\mathbf{u}_j}{\|\mathbf{u}_j\|}
end for
It's only a subtle difference in the code. -- Jitse Niesen (talk) 13:26, 14 June 2007 (UTC)

Yes, I got the difference:-) Thanks for the answer. Though I'm still thinking about the why...Raneko 10:20, 15 June 2007 (UTC)

[edit] modified gram-schmidt

It'd be nice to go over the distinction between classical and modified gram-schmidt. If anyone's interested in writing it up, the following PDF is a decent example to follow: http://www-math.mit.edu/~persson/18.335/lec5handout6pp.pdf Lavaka (talk) 01:04, 3 January 2008 (UTC)