I totally disagree with the answers given previously. The authors confuse the Frobenius normal form with the primary rational canonical form.
The Frobenius decomposition has the following form
$F:=diag(C_{p_1},\cdots,C_{p_k})$ where the $C_{p_i}$ are the companion matrices of the polynomial $p_i$, and overall, $p_i$ is a divisor of $p_{i+1}$. In particular, $p_k$ is the minimal polynomial and $p_1\cdots p_k$ is the characteristic polynomial of $A$.
When the eigenvalues of $A$ are distinct, then the vector $(1,\cdots,1)$ is cyclic over whole vector space $K^n$.
Then the Frobenius form of $A$ is $F=C_p$ where $p$ is the characteristic polynomial of $A$.
It suffices to convince oneself to test in Maple
"FrobeniusForm (DiagonalMatrix ([1,2,3]);"
I'm not sure how this is taught elsewhere, but to me it is much easier to understand step two in terms of the invariant factors of the associated characteristic matrix (so of $xI-A$ where $A$ is the matrix representation of $\phi$).
So here is a small explicit example where the matrix is already in rational canonical form, but I will point out the different steps:$$ A = \left(\begin{matrix}0\\&0\\&1&0\\&&&0&\\&&&1&0\\&&&&&1\end{matrix}\right). $$
The minimal polynomial is $x^2(x-1)$, so step 1 is to find the blocks associated with $x^2$ and $x-1$, this you say you have no problem understanding, and so we have $$A_1 =\left(\begin{matrix}0\\&0\\&1&0\\&&&0&\\&&&1&0\end{matrix}\right)$$ is associated with $x^2$ and $$A_2=(1)$$ is associated with $x-1$.
Now in the given example the decomposition of the space associated with $x-1$ is finished, but we can decompose the space associated with $x^2$ further: it should be easy to see that there are three linearly independent characteristic vectors associated with this space, and therefore we must have three indecomposable subspaces (in this example you can already see the three matrices associated with each of the subspaces, and in fact since the minimum polynomial is $x^2$ we know the largest subspace must have dimension 2, and since $A_1$ is order 5 there is then really only one way to split it into 3 indecomposable subspaces)
BUT there could be more complicated scenarios where it could be more difficult ...so how to construct these...for me the easiest way here is to use the Smith normal form of $xI-A_1$: $$xI-A_1 = \left(\begin{matrix}x\\&x\\&-1&x\\&&&x&\\&&&-1&x\end{matrix}\right)$$ has Smith normal form $$ \left(\begin{matrix}1\\&1\\&&x\\&&&x^2&\\&&&&x^2\end{matrix}\right).$$ If you read the link you will see that this form is determined by dividing the greatest common divisor among successive orders of subdeterminants of the characteristic matrix, and it always gives you a diagonal form with the "invariant factors" on the diagonal. These factors have some amazing properties including that they are invariant with respect to the underlying field, i.e. a matrix over the smallest field in a chain will have the same invariant factors as all containing fields.
Each invariant factor also divides the next and the last entry on the diagonal is the minimal polynomial. Multiplying the invariant factors yields the characteristic polynomial, but I digress...
To make a long story short, from theory it can be proved that the companion matrices of the nonconstant diagonal entries of this Smith normal form gives you exactly step 2, so $C(x), C(x^2), C(x^2)$ are the matrices associated with the nondecomposable subspaces we are looking for: in this simple example we already have these three blocks on the diagonal.
I hope this helps to answer your question: so typically for me finding the rational canonical form involves calculating the Smith normal form of the characteristic matrix...it gives you the number and dimensions of the $U_i^{(j)}$ as you would need, but it does not give you the change of basis matrix that would produce the transformation...in most cases this is not necessary though.
Final remark, the $U_i^{(j)}$ are formally known as elementary divisors. You can replace step 1 and 2 by calculating the Smith normal form of $xI-A$ directly - as the Smith normal form yields the elementary divisors (a good source that explains this very clearly), and then you can apply 3 directly.
Best Answer
Your work is fine. However, it is very ad hoc. If you are interested in a more algorithmic way of computing rational canonical forms, read on.
There are actually two things that have the right to be called the "Rational Canonical Form", the one obtained through invariant factors (what most people consider the rational canonical form) and the one obtained from elementary divisors (more akin to the Jordan form). I'll describe how to compute the elementary divisors and then get the invariant factors from them.
Example: Say we are in a real vector space. Suppose $p(x) = x^2+1$ and we compute the $r$ numbers to be $r_1 = 3, r_2 = 3, r_3 = 1, r_4 = 1, r_5 = 0$.
The dot diagram would be:
\begin{array}{lll} \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \\ \cdot \\ \cdot \\ \end{array}
The elementary divisors corresponding to $x^2+1$ would then be $(x^2+1)^4, (x^2+1)^2, (x^2+1)^2$.
To obtain the rational canonical form via elementary divisors, do this for each irreducible factor of the minimal polynomial, and then populate a matrix with the companion matrices of elementary divisors along the diagonal.
For example: Suppose the elementary divisors corresponding to $x^2+1$ are as above, and the elementary divisors corresponding to $x-2$ are: $(x-2)^3, (x-2)$. And that these are the only irreducible factors of the the minimal polynomial.
Then the invariant factors are $$(x^2+1)^4(x-2)^3, (x^2+1)^2(x-2), (x^2+1)^2.$$
To obtain the rational canonical form via invariant factors, populate a matrix with companion matrices of the invariant factors along the diagonal.
In your problem, the only irreducible factor of the minimal polynomial is $(t-1)$. Let's compute its dot diagram.
$$ r_1 = \frac{1}{1}(3 - rank(A - I)) = (3 - 1) = 2 \\ r_2 = \frac{1}{1}(rank(A-I) - rank((A-I)^2)) = (1 - 0) = 1 \\ r_3 = \frac{1}{1}(rank((A-I)^2) - rank((A-I)^3) = (0 -0) = 0$$
So the dot diagram is
\begin{array}{ll} \cdot & \cdot \\ \cdot \\ \end{array}
Therefore the elementary divisors are $(t-1)^2, (t-1)$. In this case, since there is only one irreducible factor of the minimal polynomial, the invariant factors are the same as the elementary divisors. Anyway, we get that the rational canonical form (via elementary divisors and invariant factors) is:
$$\begin{pmatrix} 0 & -1 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$
just as you had.